在 DepthFirstSearch 中寻找目标

Question

我只是想知道把这段代码放在哪里

if(node == goal){
            System.out.print("Found path: ");
            for(int n : stack){
                System.out.print(n + " ");
            }
        }

在这个方法中：

public void performRecursiveDFS(Graph G, int node, int goal) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(node);
    while (!stack.isEmpty()) {
        node = stack.pop();
         if (!visited[node]) {
            visited[node] = true;
            for (int w : G.adjList(node)) {
                stack.push(w);
            }
        }
    }
}

原因是，我想打印从起始节点到目标节点的路径。比如像这样，Found path: 0 1 2 3 4 7。我试着把它放在 node = stack.pop() 之后，但它向我显示了类似 Found path: 3 的内容。有 reason/suggestion 吗？我的代码有问题吗？如果是这样，请详细指导我。欢迎提问。提前致谢。

Answer 1

堆栈当前正在存储要检查的下一个节点，而不是已经检查到当前点的节点。

要获取路径，您需要创建一个列表并将选中的每个节点添加到该列表。

一旦你得到一个节点，你可以检查该节点是否是目标节点，然后你可以打印出列表

Answer 2

您已经实施了 DFS 的一部分来跟踪访问的节点，您可以扩展它以了解源路径，也就是 link 到下一个节点

完整的 DFS 实现如下所示，它也将处理路径请求

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;


public class DirectedDFS {

    private final Digraph g;
    private final int source;

    private boolean[] marked;
    private int[] edgeFrom;

    public DirectedDFS(Digraph g, int source) {
        this.g = g;
        this.source = source;
        init(g);
        dfs(g, source);
    }

    private void init(Digraph g) {
        this.marked = new boolean[g.V()];
        this.edgeFrom = new int[g.V()];
        Arrays.fill(edgeFrom, -1);
    }

    private void dfs(Digraph g, int source) {

        marked[source] = true;
        for (int vertex : g.adj(source)) {
            if (!marked[vertex]) {
                edgeFrom[vertex] = source;
                dfs(g, vertex);
            }
        }
    }

    public boolean hasPath(int v) {
        return marked[v];
    }

    public Iterable<Integer> path(int v) {
        if (hasPath(v)) {
            final Deque<Integer> paths = new ArrayDeque<>();
            int vertex = v;
            paths.push(v);
            while ((vertex = edgeFrom[vertex]) != -1) {
                paths.push(vertex);
            }
            return paths;
        }
        return (Iterable<Integer>) Collections.emptyIterator();
    }

}

Answer 3

您目前没有存储当前节点的路径，因此无法打印它。实现此目的的一种相当简单的方法是使用地图绘制返回原点的路径。这可以代替您对 visited 数组的使用。

这是它的样子：

public void performRecursiveDFS(Graph G, int start, int goal) {
    Stack<Integer> remaining = new Stack<Integer>();
    remaining.push(start);
    Map<Integer, Integer> previous = new HashMap<>();
    while (!remaining .isEmpty()) {
        int current = remaining.pop();
        if (current == goal) {
            Deque<Integer> path = new LinkedList<>();
            path.addFirst(current);
            while (previous.containsKey(path.peek())
                path.addFirst(previous.get(path.peek()));
            // print path
        } else if (!previous.containsKey(current)) {
            for (int w : G.adjList(current)) {
                previous.put(w, current);
                remaining.push(w);
            }
        }
    }
}

在 DepthFirstSearch 中寻找目标

Finding goal in DepthFirstSearch

java

stack

graph-algorithm

path-finding

depth-first-search