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

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

如果有人关心的话，问题在于我完全无视ArrayList有一个“IndexOf（）”方法的事实（我知道这很愚蠢），决定将我自己的“index”字段破解到我的节点类中。在处理我自己的索引时，我有一个小错误，它破坏了遍历

因此，我的DFS算法中的旧行如下所示：

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

但它应该是：

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

Answer 2

你说对了。如果从堆栈中弹出一个节点，则需要确保其所有未访问的邻居首先都在堆栈中。否则，无法保证每个人都会被访问

例如，在您给出的第一个图中，如果先访问节点A，然后访问节点B，那么接下来将访问节点C或D。但是，如果只将其中一个推到堆栈上，然后移除B，则无法到达最后一个

因此，您可能需要编写一个函数getAllInvisitedAdjacentNodes，并在弹出之前将它们全部推到堆栈上