2

所以我写了一个 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;
    }
}
4

2 回答 2

2

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

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

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

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

但它应该是：

int nextNode = this.getUnvisitedAdjacentNode(this.nodeList.indexOf(stack.peek()));
于 2012-08-22T00:51:05.223 回答
1

你说的。如果你从堆栈中弹出一个节点，你需要确保它所有未访问的邻居都在堆栈上。否则，不能保证每个人都会被访问。

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

因此，您可能想要编写一个函数 getAllUnvisitedAdjacentNodes 并在弹出之前将它们全部压入堆栈。

于 2012-08-22T00:41:27.383 回答