算法导论之深度优先搜索

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>
热门搜索

算法导论之深度优先搜索
