深度优先搜索可以解决单点路径问题，即给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径。”等类似问题。

以下算法实现中edgeTo[]记住每个顶点到起点的路径。

使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径的长度成正比。

代码

其中图用到了Graph：

package section4_1;

import java.util.ArrayList;
import java.util.List;

public class DepthFirstPaths {

    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G,s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G,w);
            }
        }
    }

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

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        List<Integer> list = new ArrayList<>();
        for (int x = v;x != s;x = edgeTo[x]) {
            list.add(0,x);
        }
        list.add(0,s);
        return list;
    }

    public static void main(String[] args) {
        int[][] data = {
                {0,5},
                {2,4},
                {2,3},
                {1,2},
                {0,1},
                {3,4},
                {3,5},
                {0,2}
        };
        int v = 6;
        int e = 8;
        Graph graph = new Graph(v,e,data);
        DepthFirstPaths dfs = new DepthFirstPaths(graph,0);
        for (int x : dfs.pathTo(5)) {
            System.out.print(x + " ");
        }
    }

}