Блог

Главная - Вопросы по программированию - Что не так с моим итератором графика через DFS?

Что не так с моим итератором графика через DFS?

#java #algorithm #graph #iterator

#java #алгоритм #График #итератор

Вопрос:

Я пытался упростить, DFS используя объектно-ориентированный дизайн и реализуя Iterator класс. Но DFS работает не так, как должно.

Я почти перепробовал все, что мог, но мне не удалось заставить это работать.

Также я не смог найти много соответствующей информации в Интернете о типе кода, который я пытаюсь.

У меня есть два интерфейса Vertex и Graph .

Ниже приведен код, который я пытаюсь:

 public class GraphIterator implements Iterator<Vertex> {
  private Graph g;
  private Vertex v;
  private Stack<Vertex> stack;
  private Set<Vertex> colored;

  public GraphIterator(Graph g, Vertex v) {
      this.g = g;
      this.v = v;
      stack = new Stack<>();
      colored = new TreeSet<>();
      stack.push(v);
      colored.add(v);
  }

  @Override
  public boolean hasNext() {
    return stack.isEmpty();
  }

  @Override
  public Vertex next() {
    Vertex u = stack.pop();

    for(Vertex vertex : g.getNeighbours(u)) {
        if(vertex != null amp;amp; !colored.contains(vertex))
            stack.add(vertex);
    }

    return stack.pop();
  }
}

Это код, в main() котором я пытаюсь протестировать:

 GraphClass g = new GraphClass();
Vertex v = new VertexClass(0);
Vertex w = new VertexClass(1);
g.addVertex(v);
g.addVertex(w);
g.addEdge(v, w);
Iterator<Vertex> it = new GraphIterator(g, v);
System.out.println(v " vs " it.next());
System.out.println(it.hasNext());
System.out.println(w " vs " it.next());

Я знаю, что делаю что-то не так с DFS алгоритмом, но я не могу до конца понять, что и где я делаю не так?

Я в основном уверен, что я делаю что-то не так с DFS алгоритмом, который необходимо реализовать с использованием переопределенных методов из Iterator класса. Я также был бы признателен за несколько советов о том, как это сделать.

Я был бы признателен, если бы кто-нибудь мог помочь мне в этом алгоритме.

Комментарии:

1. Можете ли вы показать модульный тест? Как выглядит график?

2. @cricket_007 На данный момент у меня нет модульных тестов, это просто неориентированный простой граф с вершинами

3. Хорошо, тогда вы можете показать пример ввода графика?

4. Вы реализовали equals и hashcode в классе реализации vertex? В противном случае метод set contains не будет работать

5. Предоставление полного выполняемого / тестируемого кода было бы намного проще как для вас, так и для других, чтобы помочь в решении вопроса, а тестовый пример сделал бы все более понятным и простым.

Ответ №1:

Возможные улучшения рассматриваемого кода:

  • В next() , может быть, просто return u; , вместо return stack.pop(); .
    Потому что это привело бы к появлению 2 элементов за один вызов next() , а соседние вершины второго не были отмечены.
  • LinkedList может быть лучшим выбором, чем Stack здесь.
    Поскольку, похоже, нет необходимости в параллельном управлении.

Кстати:

  • LinkedList это тоже стек, он не потокобезопасен; в то время как Stack потокобезопасен.
  • (Если бы можно было опубликовать код в блоке, который другие могут копировать и запускать напрямую, и видеть результат, тогда, вероятно, можно было бы предоставить лучший ответ.)