java - 改变深度优先搜索的方向

Question

我只是想知道，是否可以改变深度优先搜索的方向？我必须找到从起始节点到目标节点的路径。这是我的深度优先搜索结果的样子。 0 5 7 8 9 10 6 4 1 3 2 11。起始节点是0，目标节点是1。我想要的路径是0 5 4 1。在深度优先搜索中方向真的很重要吗？这是我的代码:

public void performIterativeDFS(Graph G, int node, int goal) {
    ArrayBasedStack arrayStack = new ArrayBasedStack();
    arrayStack.push(node);
    visited[node] = true;
    while (!arrayStack.isEmpty()) {
        int n = arrayStack.pop();
        System.out.print(n + " ");
        for (int w : G.adjList(n)) {
            if (!visited[w]) {
                visited[w] = true;
                arrayStack.push(w);
                if (w == goal) {
                    goal = w;
                    System.out.print(" Goal Found: ");
                }
            }
        }
    }
}

结构:

11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
0 5

Answer 1

只要有可能选择，DFS 就会随机选择一个方向，并沿该方向继续，标记先前的位置，直到遇到路障。我不确定你如何以及为何控制这个方向。但是，如果您正在寻找最短路径，请使用广度优先搜索(BFS)来做到这一点。它会在继续前进之前系统地探索附近的节点，并为您提供最佳路径。