2019獨角獸企業重金招聘Python工程師標準>>>

package org.loda.graph;import org.loda.structure.Stack;/*** * @ClassName: DFS * @Description: 深度優先搜索（無向圖） * @author minjun * @date 2015年5月24日 上午4:02:24 **/ public class DFS {//原點private int s;// visited[i]表示i節點是否被訪問過private boolean[] visited;// prev[i]表示沿著一條路徑到i時，這條路徑上i的上一個節點private int[] prev;public DFS(int s,Graph g){//初始化this.s=s;int v=g.v();visited=new boolean[v];prev=new int[v];for(int i=0;i<v;i++){prev[i]=-1;}dfs(s,g);}private void dfs(int v, Graph g) {//訪問節點visited[v]=true;//查找v所有的鄰接節點for(int w:g.adj(v)){//找到沒有訪問過的節點if(!visited[w]){prev[w]=v;dfs(w, g);}}}public boolean hasPathTo(int v){return visited[v];}public Iterable<Integer> pathTo(int v){if(!hasPathTo(v)) return null;Stack<Integer> path=new Stack<Integer>();for(int i=v;i!=s;i=prev[i]){path.push(i);}path.push(s);return path;}public static void main(String[] args) {//原點int s=0;//頂點數目int n=6;Graph g=new Graph(n);//將頂點添加到圖中g.add(0, 5);g.add(2, 4);g.add(2, 3);g.add(1, 2);g.add(0, 1);g.add(3, 4);g.add(3, 5);g.add(0, 2);DFS bfs=new DFS(s, g);for(int i=0;i<n;i++){Iterable<Integer> path=bfs.pathTo(i);System.out.print("從原點"+s+"到"+i+"的可達路徑為：");if(path==null){System.out.println("不可達");}else{for(int j:path){System.out.print(j+"->");} // System.out.println("\t統計得到的距離為"+bfs.distTo(i));System.out.println();}}} }輸出內容為：從原點0到0的可達路徑為：0-> 從原點0到1的可達路徑為：0->2->1-> 從原點0到2的可達路徑為：0->2-> 從原點0到3的可達路徑為：0->2->3-> 從原點0到4的可達路徑為：0->2->3->4->

從原點0到5的可達路徑為：0->2->3->5->???????

轉載于:https://my.oschina.net/u/1378920/blog/418998

總結

以上是生活随笔為你收集整理的算法导论——DFS深度优先搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。