独角兽企业重金招聘Python工程师标准>>>
package org.loda.graph;import org.loda.structure.Stack;/*** * @ClassName: DFS * @Description: 深度优先搜索（无向图） * @author minjun* @date 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->
从原点0到5的可达路径为：0->2->3->5->
如果觉得《算法导论——DFS深度优先搜索》对你有帮助，请点赞、收藏，并留下你的观点哦！
