寻路算法

算法"/>

寻路算法

图的寻路算法也可以通过深度优先遍历 dfs 实现，寻找图 graph 从起始 s 点到其他点的路径，在上一小节的实现类中添加全局变量 from数组记录路径，from[i] 表示查找的路径上i的上一个节点。

首先构造函数初始化寻路算法的初始条件，from = new int[G.V()] 和 from = new int[G.V()]，并在循环中设置默认值，visited 数组全部为false，from 数组全部为 -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 数组往上追溯就能找到所有的路径。

...
Vector<Integer> path(int w){assert hasPath(w) ;Stack<Integer> s = new Stack<Integer>();// 通过from数组逆向查找到从s到w的路径, 存放到栈中int p = w;while( p != -1 ){s.push(p);p = from[p];}// 从栈中依次取出元素, 获得顺序的从s到w的路径Vector<Integer> res = new Vector<Integer>();while( !s.empty() )res.add( s.pop() );return res;
}
...

Java 实例代码

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中Vector<Integer> path(int w){assert hasPath(w) ;Stack<Integer> s = new Stack<Integer>();// 通过from数组逆向查找到从s到w的路径, 存放到栈中int p = w;while( p != -1 ){s.push(p);p = from[p];}// 从栈中依次取出元素, 获得顺序的从s到w的路径Vector<Integer> res = new Vector<Integer>();while( !s.empty() )res.add( s.pop() );return res;}// 打印出从s点到w点的路径void showPath(int w){assert hasPath(w) ;Vector<Integer> 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();elseSystem.out.print(" -> ");}}
}