package _07._06;import java.util.Vector;
import java.util.Stack;public class Path {private Graph G; // 圖的引用private int s; // 起始點private boolean[] visited; // 記錄dfs的過程中節點是否被訪問private int[] from; // 記錄路徑, from[i]表示查找的路徑上i的上一個節點// 圖的深度優先遍歷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(" -> ");}}
}
圖文件
8 7
0 1
0 3
0 2
3 4
3 5
2 6
2 7
測試代碼
package _07._06;public class Main {// 測試尋路算法public static void main(String[] args) {String filename = "testG.txt";SparseGraph g = new SparseGraph(8, false);ReadGraph readGraph = new ReadGraph(g, filename);g.show();System.out.println();Path path = new Path(g,0);System.out.println("Path from 0 to 6 : ");path.showPath(6);}
}
