给定一幅图和起点 s ，回答从起点 s 到任意目的地点 v 是否存在一条路径？如果有，找出这条路径。

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class DepthFirstPaths {

    /**
     * 在 graph 找出所有起点为 s 的路径
     */
    public DepthFirstPaths(Graph graph, int s);

    /**
     * 是否存在一条 s-v 的路径
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 如果存在一条 s-v 的路径，则返回该路径，否则返回 null
     */
    public Iterable<Integer> pathTo(int v)
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class DepthFirstPaths {

    private boolean[] marked;

    private int[] edgeTo;

    /**
     * 起点
     */
    private int s;

    /**
     * 在 graph 找出所有起点为 s 的路径
     */
    public DepthFirstPaths(Graph graph, int s) {
        marked = new boolean[graph.v()];
        edgeTo = new int[graph.v()];
        this.s = s;
        dfs(graph, s);
    }

    private void dfs(Graph graph, int s) {
        marked[s] = true;
        for (int i : graph.adj(s)) {
            if (!marked[i]) {
                edgeTo[i] = s;
                dfs(graph, i);
            }
        }
    }

    /**
     * 是否存在一条 s-v 的路径
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 如果存在一条 s-v 的路径，则返回该路径，否则返回 null
     */
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }

        Stack<Integer> path = new Stack<>();
        for (int i = v; i != s; i = edgeTo[i]) {
            path.push(i);
        }
        path.push(s);

        return path;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) {
    Graph graph = new Graph(13);
    graph.addEdge(0, 5);
    graph.addEdge(4, 3);
    graph.addEdge(0, 1);
    graph.addEdge(9, 12);
    graph.addEdge(6, 4);
    graph.addEdge(5, 4);
    graph.addEdge(0, 2);
    graph.addEdge(11, 12);
    graph.addEdge(9, 10);
    graph.addEdge(0, 6);
    graph.addEdge(7, 8);
    graph.addEdge(9, 11);
    graph.addEdge(5, 3);

    DepthFirstPaths depthFirstPaths = new DepthFirstPaths(graph, 0);

    System.out.println("path: 0 - 7 : " + depthFirstPaths.hasPathTo(7)); // path: 0 - 7 : false
    System.out.println("path: 0 - 6 : " + depthFirstPaths.hasPathTo(6)); // path: 0 - 6 : true
    Iterable<Integer> path = depthFirstPaths.pathTo(6);
    for (int i : path) {
        System.out.print(i);
        if (i != 6) {
            System.out.print(" | "); // 0 | 5 | 4 | 6
        }
    }
}