java - 通过 DFS 我的图形迭代器有什么问题？

Question

我一直在尝试使用面向对象的设计和实现 Iterator 类来制作简单的 DFS。但是 DFS 没有正常工作。

我几乎已经尝试了所有可能的方法，但我无法完成这项工作。

此外，我在互联网上找不到太多关于我正在尝试的代码类型的相关信息。

我有两个接口(interface) 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 && !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 类中的重写方法来实现。我也很感激一些关于如何这样做的提示。

如果有人能在这个算法中帮助我，我将不胜感激。

Answer 1

对相关代码的可能改进:

• 在next()中，可能只是return u;，而不是return stack.pop();。
  因为这会在对 next() 的一次调用中弹出 2 个元素，并且第二个的相邻顶点未选中。
• LinkedList 可能是比 Stack 更好的选择。
  因为似乎不需要并发控制。

顺便说一句:

• LinkedList 也是一个栈，它不是线程安全的；而 Stack 是线程安全的。
• (如果能把代码贴在一个block里，其他人可以直接复制运行，看输出结果，可能会有更好的答案。)