算法导论之深度优先搜索，导论深度优先搜索,import org.l

算法导论之深度优先搜索，导论深度优先搜索,import org.l

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>