java - 图深度优先搜索有时有效，有时无效

Question

所以我写了一个 Graph 类，我似乎无法根据节点的顺序正确地对它进行深度优先搜索。这就是我的意思:

如果我的图表如下所示:

A-B-D
|/
C

DFS 返回:“ABC”

但是当它看起来像这样时:

A-B
| |
D C
|
E

它将正确打印 ABCDE。

我发现的问题在于我的 getUnvisitedAdjacentNode() 函数。这是函数:

    public int getUnvisitedAdjacentNode(int n) {
    for (int i = 0; i < this.nodeList.size(); i++) {
        if (this.edges[n][i] == 1 && this.nodeList.get(i).wasVisited == false) {
            return i;
        }
    }
    return -1;
}

我发现的问题是因为它按“顺序”(只是一个 for 循环)进行，在第一种情况下它永远不会遍历 D，因为 B 被访问，而在 C 被访问后，B 只是从堆栈中弹出.也许这不是问题。

这是我实际的 DFS 遍历的代码。

   public void depthFirstTraverse() {
    Stack<Node> stack = new Stack<Node>();

    nodeList.get(0).wasVisited = true;
    System.out.println(nodeList.get(0).item);
    stack.push(nodeList.get(0));

    while (!stack.isEmpty()) {
        int nextNode = this.getUnvisitedAdjacentNode(stack.peek().index);

        if (nextNode == -1) {
            stack.pop();
        } else {
            nodeList.get(nextNode).wasVisited = true;
            System.out.println(nodeList.get(nextNode).item);
            stack.push(nodeList.get(nextNode));
        }
    }
    for (int i = 0; i < nodeList.size(); i++) {
        nodeList.get(i).wasVisited = false;
    }
}

Answer 1

还好我自己发现了错误，上面的代码都是正确的，只是代码中我没有粘贴。

万一有人关心，问题在于我完全无视ArrayLists有一个“IndexOf()”方法的事实(愚蠢，我知道)并决定将我自己的“index”字段黑进我的Node类。在处理我自己的索引时，我有一个小错误，它搞砸了遍历。

所以我的 DFS 算法中的旧行如下所示:

int nextNode = this.getUnvisitedAdjacentNode(stack.peek().index);

但它应该是:

int nextNode = this.getUnvisitedAdjacentNode(this.nodeList.indexOf(stack.peek()));