织梦网站转跳手机站,注册公司代理记账费用,制作网站开发用的图片,网站怎样做反向链接目录 广度优先遍历与最短路径
Java 实例代码
src/runoob/graph/ShortestPath.java 文件代码#xff1a; 广度优先遍历与最短路径
广度优先遍历从某个顶点 v 出发#xff0c;首先访问这个结点#xff0c;并将其标记为已访问过#xff0c;然后顺序访问结点v的所有未被访问…目录 广度优先遍历与最短路径
Java 实例代码
src/runoob/graph/ShortestPath.java 文件代码 广度优先遍历与最短路径
广度优先遍历从某个顶点 v 出发首先访问这个结点并将其标记为已访问过然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} 并将其标记为已访问过然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法直到所有结点都被访问完为止。
我们可以分为三个步骤
1使用一个辅助队列 q首先将顶点 v 入队将其标记为已访问然后循环检测队列是否为空。2如果队列不为空则取出队列第一个元素并将与该元素相关联的所有未被访问的节点入队将这些节点标记为已访问。3如果队列为空则说明已经按照广度优先遍历了所有的节点。
下图所示右边蓝色表示从 0 开始遍历节点的顺序下面是记录距离 0 的距离可知广度优先遍历能求出无权图的最短路径。 下面用代码展示如何用广度优先遍历方式完成遍历并且查询到最短路径。我们在上一小节代码的基础上增加一全局变量 ord 数组记录路径中节点的次序。ord[i] 表示 i 节点在路径中的次序。同时构造函数做出相应调整在遍历相邻节点时 每访问一个未被访问的节点进行 ord[i] ord[v] 1记录距离。邻接表的广度优先遍历时间复杂度为 O(VE)邻接矩阵的时间复杂度为O(V^2)。
... // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public ShortestPath(Graph graph, int s){ // 算法初始化 G graph; assert s 0 s G.V(); visited new boolean[G.V()]; from new int[G.V()]; ord new int[G.V()]; for( int i 0 ; i G.V() ; i ){ visited[i] false; from[i] -1; ord[i] -1; } this.s s; // 无向图最短路径算法, 从s开始广度优先遍历整张图 LinkedListInteger q new LinkedListInteger(); q.push( s ); visited[s] true; ord[s] 0; while( !q.isEmpty() ){ int v q.pop(); for( int i : G.adj(v) ) if( !visited[i] ){ q.push(i); visited[i] true; from[i] v; ord[i] ord[v] 1; } } } ...
查看从 s 点到 w 点的最短路径长度若从 s 到 w 不可达返回-1。
... public int length(int w){ assert w 0 w G.V(); return ord[w]; } ...
Java 实例代码
源码包下载Download
src/runoob/graph/ShortestPath.java 文件代码
package runoob.graph; import runoob.graph.read.Graph; import java.util.LinkedList; import java.util.Stack; import java.util.Vector; /** * 广度优先遍历与最短路径 */ public class ShortestPath { // 图的引用 private Graph G; // 起始点 private int s; // 记录dfs的过程中节点是否被访问 private boolean[] visited; // 记录路径, from[i]表示查找的路径上i的上一个节点 private int[] from; // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。 private int[] ord; // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public ShortestPath(Graph graph, int s){ // 算法初始化 G graph; assert s 0 s G.V(); visited new boolean[G.V()]; from new int[G.V()]; ord new int[G.V()]; for( int i 0 ; i G.V() ; i ){ visited[i] false; from[i] -1; ord[i] -1; } this.s s; // 无向图最短路径算法, 从s开始广度优先遍历整张图 LinkedListInteger q new LinkedListInteger(); q.push( s ); visited[s] true; ord[s] 0; while( !q.isEmpty() ){ int v q.pop(); for( int i : G.adj(v) ) if( !visited[i] ){ q.push(i); visited[i] true; from[i] v; ord[i] ord[v] 1; } } } // 查询从s点到w点是否有路径 public boolean hasPath(int w){ assert w 0 w G.V(); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 public VectorInteger path(int w){ assert hasPath(w) ; StackInteger s new StackInteger(); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p w; while( p ! -1 ){ s.push(p); p from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 VectorInteger res new VectorInteger(); while( !s.empty() ) res.add( s.pop() ); return res; } // 打印出从s点到w点的路径 public void showPath(int w){ assert hasPath(w) ; VectorInteger vec path(w); for( int i 0 ; i vec.size() ; i ){ System.out.print(vec.elementAt(i)); if( i vec.size() - 1 ) System.out.println(); else System.out.print( - ); } } // 查看从s点到w点的最短路径长度 // 若从s到w不可达返回-1 public int length(int w){ assert w 0 w G.V(); return ord[w]; } }
