如何使用dfs从图中一个顶点到其他每个顶点找到路径？

Question

从给定的顶点开始，如何设置使用DFS的算法以查找从有向图上的一个顶点到其他每个顶点的路径？

我设置了一个图形，并且在Java中具有邻接表。

Answer 1

是DAG吗？

如果是，那么您可以通过回溯找到所有可能的路径，尽管复杂度将是指数级的。

public static void backTrack(int u,ArrayList<Integer> path){
// assuming adj[i] is the adjacency list of node if
// u is the current node

    if(adj[u].size() == 1){ // if leaf node is reached
       path.add(u);
       /// you got a path from root to u, do whatever you want 
       return ;
    }

    for(int v : adj[u]) {
        ArrayList<Integer> tmp = new ArrayList<Integer>(path);
        tmp.add(u);
        backTrack(v,tmp);
    }
}

如果图形具有循环，则它将陷入无限循环。

希望有帮助。