0106广度优先搜索和最短路径-无向图-数据结构和算法(Java)_在某无向图中求距离顶点v的最短路径长度深度和广度优先遍历算法哪个更合适

1 单点最短路径

单点最短路径。 给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）。“等类似问题。

深度优先搜索在这个问题上没有什么作为，因为它遍历整个图的顺序和找出最短路径的目标没有任何关系。相比之下，广度优先搜索正好可以解决这个问题。

分析：

• 要找的从s到v的最短路径，从s开始，在所有由一条边就可以到达的顶点中寻找v，找到标记结束。
• 如果没有找到，我们继续在于s距离2条边的顶点中查找v，如此一直进行。
• 最后也没有找到，那么说明s到给定顶点v不存在路径，此图为非连通图。

结构选择：

• 广度优先搜索中，我们希望按照与起点的距离顺序遍历所有顶点，所以我们选择队列（先入先出）。

2 广度优先搜索实现

实现代码如下：

package com.gaogzhen.datastructure.graph.undirected;

import edu.princeton.cs.algs4.*;

/**
 * 最短路径算法
 * @author: Administrator
 * @createTime: 2023/03/07 21:04
 */
public class BreadthFirstDirectedPaths {
    private static final int INFINITY = Integer.MAX_VALUE;

    /**
     * 标记顶点是否与起点连通
     */
    private boolean[] marked;

    /**
     * 表示顶点到与该顶点连通的顶点间最短路径
     */
    private int[] edgeTo;

    /**
     * 顶点到起点之间的边数
     */
    private int[] distTo;

    /**
     * 计算从指定顶点到起点最短路径
     * @param G 无向图
     * @param s 起点
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public BreadthFirstDirectedPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = INFINITY;
            edgeTo[v] = -1;
        }
        validateVertex(s);
        bfs(G, s);
    }

    /**
     * 计算多个起点到指定顶点之间的最短路径
     * @param G 无向图
     * @param sources 多个起点集合
     * @throws IllegalArgumentException if {@code sources} is {@code null}
     * @throws IllegalArgumentException unless each vertex {@code v} in
     *         {@code sources} satisfies {@code 0 <= v < V}
     */
    public BreadthFirstDirectedPaths(Graph G, Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = INFINITY;
            edgeTo[v] = -1;
        }
        validateVertices(sources);
        bfs(G, sources);
    }

    /**
     * 广度优先搜索从指定顶点到起点最短路径
     * @param G 无向图
     * @param s 起点
     */
    private void bfs(Graph G, int s) {
        Queue<Integer> q = new Queue<Integer>();
        marked[s] = true;
        distTo[s] = 0;
        q.enqueue(s);
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }

    // BFS from multiple sources
    private void bfs(Graph G, Iterable<Integer> sources) {
        Queue<Integer> q = new Queue<Integer>();
        for (int s : sources) {
            marked[s] = true;
            distTo[s] = 0;
            q.enqueue(s);
        }
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }

    /**
     * 起点s与指定顶点v之间是否有路径（连通）
     * @param v the vertex
     * @return {@code true} if there is a directed path, {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }

    /**
     * 返回指定顶点v到起点直接的最短路径（边数）}?
     * @param v the vertex
     * @return the number of edges in such a shortest path
     *         (or {@code Integer.MAX_VALUE} if there is no such path)
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public int distTo(int v) {
        validateVertex(v);
        return distTo[v];
    }

    /**
     * 返回指定顶点v到起点直接的最短路径，没有返回null
     * @param v the vertex
     * @return the sequence of vertices on a shortest path, as an Iterable
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public Iterable<Integer> pathTo(int v) {
        validateVertex(v);

        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        int x;
        for (x = v; distTo[x] != 0; x = edgeTo[x])
            path.push(x);
        path.push(x);
        return path;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    // throw an IllegalArgumentException if vertices is null, has zero vertices,
    // or has a vertex not between 0 and V-1
    private void validateVertices(Iterable<Integer> vertices) {
        if (vertices == null) {
            throw new IllegalArgumentException("argument is null");
        }
        int V = marked.length;
        int count = 0;
        for (Integer v : vertices) {
            count++;
            if (v == null) {
                throw new IllegalArgumentException("vertex is null");
            }
            validateVertex(v);
        }
        if (count == 0) {
            throw new IllegalArgumentException("zero vertices");
        }
    }
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

队列保存所有已被标记但其邻接表未被检查过的顶点。先将起点加入队列，然后重复一下步骤知道队列为空。

• 取出队列中的下一个顶点v并标记它。
• 将与v相邻的所有未被标记过的顶点加入队列。

说明：

• edgeTo[]数组结果，也是一棵用父链接表示的根结点为s的树
  • 多起点中，则以各自起点为根结点的树组成的森林。
• distTo[]表示到起点的路径长度，即边数。代码distTo[w] = distTo[v] + 1;当前顶点路径长度为其父顶点路径长度+1，起点为0。
• 与算法第四版不同的地方只是在初始化edgeTo为-1表示根结点；算法第四版默认都是0。

以之前无向图（6个顶点，8条边）为例单起点搜索索引起点为0（单起点的路径结果：

多起点（0,2）搜索结果如下图所示：

多起点搜索很少用到，一般情况下我们讨论最短路径默认为单点最短路径。

3 总结

命题B。对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径（没有其他从s到v的路径所含有的边比这条路径少。

证明：由归纳易得队列总是包含林哥或者多个到起点的距离为k的顶点，之后是零个或者多个到起点为k+1的顶点，k为整数，起始值为0.这意味着顶点是按照它们和s的距离顺序加入或者离开队列。从顶点v加入队列到它离开队列之前，不可能找出到v的更短路径，而在v离开队列之后发现的所有能够到达v的路径都不可能短于v在树中的路径长度。

命题B（续）。广度优先搜索所需的时间在最坏情况下和V+E成正比。

证明：广度优先搜索标记所有与s连通的顶点所需的时间与它们的度数之和成正比。如果图是连通的，这个和就是所有顶点的度数之和，也就是2E。

广度优先搜索也可以解决单点连通问题，它检查所有与起点连通的顶点和边的方法取决于查找的能力。代码如下：

private void bfs(Graph G, int s) {
    Queue<Integer> q = new Queue<Integer>();
    marked[s] = true;
    q.enqueue(s);
    while (!q.isEmpty()) {
        int v = q.dequeue();
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                marked[w] = true;
                q.enqueue(w);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后记

如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考链接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10.p344-348.