算法导论之深度优先搜索

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>

标签： 搜索

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。