目錄
?
尋路算法
Java 實例代碼
src/runoob/graph/Path.java 文件代碼：
?
尋路算法
圖的尋路算法也可以通過深度優先遍歷 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 實例代碼
源碼包下載：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中
? ? 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();
? ? ? ? ? ? else
? ? ? ? ? ? ? ? System.out.print(" -> ");
? ? ? ? }
? ? }
}
?
