单点最短路径 : 给定一幅图和一个起点 s, 回答从 s 到给定目的顶点 v 是否存在一条路径？如果有，找出其中最短的那条。

搜索 API

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

    /**
    * 在 graph 找出所有起点为 s 的路径
    */
    public BreadthFirstPaths(Graph graph, int s);
    
    /**
    * 是否存在一条 s-w 的路径
    */
    public boolean hasPathTo(int w);

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

实现

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
public class BreadthFirstPaths {

    private boolean[] marked;

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

    private int[] edgeTo;

    public BreadthFirstPaths(Graph graph, int s) {
        marked = new boolean[graph.v()];
        edgeTo = new int[graph.v()];
        this.s = s;
        bfs(graph, s);
    }

    private void bfs(Graph graph, int s) {
        Queue<Integer> queue = new Queue<>();
        marked[s] = true;
        queue.enqueue(s);
        while (!queue.isEmpty()) {
            int i = queue.dequeue();
            for (int j : graph.adj(i)) {
                if (!marked[j]) {
                    marked[j] = true;
                    edgeTo[j] = i;
                    queue.enqueue(j);
                }
            }
        }
    }

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

    public Iterable<Integer> pathTo(int w) {
        if (!hasPathTo(w)) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = w; i != s; i = edgeTo[i]) {
            stack.push(i);
        }
        stack.push(s);
        return stack;
    }
}

测试

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
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);

    BreadthFirstPaths depthFirstPaths = new BreadthFirstPaths(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(3);
    for (int i : path) {
        System.out.print(i);
        if (i != 3) {
            System.out.print(" | "); // 0 | 5 | 3
        }
    }

    System.out.println();

    Iterable<Integer> toSixPath = depthFirstPaths.pathTo(6);
    for (int i : toSixPath) {
        System.out.print(i);
        if (i != 6) {
            System.out.print(" | "); // 0 | 6
        }
    }
}