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ループのみ）になるためです。最初の状況では、Bが訪問され、Cが訪問された後、Bがスタックからポップされるため、Dをトラバースすることはありません。 。多分これは問題ではありません。

これが私の実際の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()" メソッドを持っているという事実を完全に無視したという事実にあり (ばか、私は知っています)、自分の "index" フィールドを 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

You said it. If you pop a node off of the stack, you need to make sure that all of its unvisited neighbors are on the stack first. Otherwise, there's no guarantee that everyone will be visited.

For example, in the first diagram you gave, if node A is visited first, and then node B, either node C or D will be visited next. However, if you only push one of them onto the stack, and then remove B, there will be no way of reaching the last one.

So what you may want to do it write a function getAllUnvisitedAdjacentNodes and push all of them onto the stack before you pop.

于 2012-08-22T00:41:27.383 に答える