import org.loda.structure.Stack;
 
/**
 * 
* @ClassName: DFS 
* @Description: 深度優(yōu)先搜索（無向圖） 
* @author minjun
* @date 2015年5月24日 上午4:02:24 
*
 */
public class DFS {
     
    //原點
    private int s;
 
    // visited[i]表示i節(jié)點是否被訪問過
    private boolean[] visited;
 
    // prev[i]表示沿著一條路徑到i時，這條路徑上i的上一個節(jié)點
    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) {
         
        //訪問節(jié)點
        visited[v]=true;
         
        //查找v所有的鄰接節(jié)點
        for(int w:g.adj(v)){
            //找到?jīng)]有訪問過的節(jié)點
            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;
        //頂點數(shù)目
        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統(tǒng)計得到的距離為"+bfs.distTo(i));
                System.out.println();
            }
        }
         
    }
}
 
 
輸出內(nèi)容為：
 
從原點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>

標簽： 搜索

版權(quán)申明：本站文章部分自網(wǎng)絡，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。