算法導論之深度優先搜索

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->
<p>
<span></span>從原點0到5的可達路徑為：0->2->3->5->

</p></pre>