0106广度优先搜索和最短路径-无向图-数据结构和算法(Java)

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 sourcesprivate 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-1private 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");}}
}

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

• 取出队列中的下一个顶点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);}}}
}

后记

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

❓QQ:806797785

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

参考链接:

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