大连建设科技网站,wordpress 相对路径,宽带收费价格,网站做百度推广划算吗1 单点最短路径 单点最短路径。 给定一幅图和一个起点s#xff0c;回答“从s到给定目的顶点v是否存在一条路径#xff1f;如果有#xff0c;找出其中最短的那条#xff08;所含边数最少#xff09;。“等类似问题。 深度优先搜索在这个问题上没有什么作为#xff0c;因为…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, IterableInteger 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) {QueueInteger q new QueueInteger();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, IterableInteger sources) {QueueInteger q new QueueInteger();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 IterableInteger pathTo(int v) {validateVertex(v);if (!hasPathTo(v)) return null;StackInteger path new StackInteger();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(IterableInteger 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的顶点之后是零个或者多个到起点为k1的顶点k为整数起始值为0.这意味着顶点是按照它们和s的距离顺序加入或者离开队列。从顶点v加入队列到它离开队列之前不可能找出到v的更短路径而在v离开队列之后发现的所有能够到达v的路径都不可能短于v在树中的路径长度。 命题B续。广度优先搜索所需的时间在最坏情况下和VE成正比。 证明广度优先搜索标记所有与s连通的顶点所需的时间与它们的度数之和成正比。如果图是连通的这个和就是所有顶点的度数之和也就是2E。 广度优先搜索也可以解决单点连通问题它检查所有与起点连通的顶点和边的方法取决于查找的能力。代码如下
private void bfs(Graph G, int s) {QueueInteger q new QueueInteger();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.
