沙市网站建设,中国菲律宾篮球比赛直播,魔智科技logo在线设计,做设计网站的工作内容目录 寻路算法
Java 实例代码
src/runoob/graph/Path.java 文件代码#xff1a; 寻路算法
图的寻路算法也可以通过深度优先遍历 dfs 实现#xff0c;寻找图 graph 从起始 s 点到其他点的路径#xff0c;在上一小节的实现类中添加全局变量 from数组记录路径#xff0c;fr…目录 寻路算法
Java 实例代码
src/runoob/graph/Path.java 文件代码 寻路算法
图的寻路算法也可以通过深度优先遍历 dfs 实现寻找图 graph 从起始 s 点到其他点的路径在上一小节的实现类中添加全局变量 from数组记录路径from[i] 表示查找的路径上i的上一个节点。
首先构造函数初始化寻路算法的初始条件from new int[G.V()] 和 from new int[G.V()]并在循环中设置默认值visited 数组全部为falsefrom 数组全部为 -1 值后面对起始节点进行 dfs 的递归处理。
... // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public Path(Graph graph, int s){ // 算法初始化 G graph; assert s 0 s G.V(); visited new boolean[G.V()]; from new int[G.V()]; for( int i 0 ; i G.V() ; i ){ visited[i] false; from[i] -1; } this.s s; // 寻路算法 dfs(s); } ...
那么判断 s 点到 w 点是否有路径只要查询 visited 对应数组值即可。
... boolean hasPath(int w){ assert w 0 w G.V(); return visited[w]; } ...
获取 s 点到 w 点的具体路径我们用 path 方法来实现先判断是否连通可调用 hasPath 方法由构造函数可知只需通过 from 数组往上追溯就能找到所有的路径。
... 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; } ...
Java 实例代码
源码包下载Download
src/runoob/graph/Path.java 文件代码
package runoob.graph; import runoob.graph.read.Graph; import java.util.Stack; import java.util.Vector; /** * 寻路 */ public class Path { // 图的引用 private Graph G; // 起始点 private int s; // 记录dfs的过程中节点是否被访问 private boolean[] visited; // 记录路径, from[i]表示查找的路径上i的上一个节点 private int[] from; // 图的深度优先遍历 private void dfs( int v ){ visited[v] true; for( int i : G.adj(v) ) if( !visited[i] ){ from[i] v; dfs(i); } } // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public Path(Graph graph, int s){ // 算法初始化 G graph; assert s 0 s G.V(); visited new boolean[G.V()]; from new int[G.V()]; for( int i 0 ; i G.V() ; i ){ visited[i] false; from[i] -1; } this.s s; // 寻路算法 dfs(s); } // 查询从s点到w点是否有路径 boolean hasPath(int w){ assert w 0 w G.V(); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 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点的路径 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( - ); } } }
