算法导论之深度优先搜索
发布时间:2020-12-14 23:19:26 所属栏目:Java 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 import org.loda.structure.Stack; /** * * @ClassName: DFS * @Description: 深度优先搜索(无向图) * @author minjun* @date 2015年5月24日 上午4:
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 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> 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |