文档章节

给定有向图,设计一个算法,找出两个结点之间是否存在一条路径

一贱书生
 一贱书生
发布于 2016/11/17 13:42
字数 334
阅读 15
收藏 0

通过图的遍历,比如深度优先或者广度优先搜索等,就能解决这个问题

从结点的其中一个出发,在遍历过程中,检查是否找到另一个结点即可

在遍历过程中,访问过的结点都应被标记为“已访问”,以避免重复访问

深度优先实现起来比较简单,递归即可

但广度优先很适合用来找最短路径,深度优先在访问临近结点之前需要先深度遍历其中一个临近结点

 

[java] view plain copy

 

  1. import java.awt.Graphics;  
  2. import java.util.LinkedList;  
  3.   
  4.   
  5. public class Search {  
  6.     class Node {  
  7.         State state;  
  8.     }  
  9.     public enum State {  
  10.         Unvisited, Visited, Visiting;  
  11.     }  
  12.     public boolean search(Graphics g, Node start, Node end) {  
  13.         LinkedList<Node> q = new LinkedList<Node> ();  
  14.         for ( Node u:((Object) g).getNodes() ) {  
  15.             u.state = State.Unvisited;  
  16.         }  
  17.           
  18.         start.state = State.Visiting;  
  19.         q.add(start);  
  20.           
  21.         Node u;  
  22.         while( !q.isEmpty() ) {  
  23.             u = q.removeFirst();  
  24.             if( null != u) {  
  25.                 for (Node v:u.getAdjacent()) {  
  26.                     if (v.state == State.Unvisited) {  
  27.                         if ( v == end) { return true;}  
  28.                         else {  
  29.                             v.state = State.Visiting;  
  30.                             q.add(v);  
  31.                         }  
  32.                     }  
  33.                 }  
  34.                 u.state = State.Visited;  
  35.             }  
  36.         }  
  37.         return false;  
  38.     }  

 

注:也可以使用深度优先,深度优先搜索实现起来比较简单,因为只需简单的递归即可。广度优先搜索很适合用来查找最短路径,而深度优先搜索在访问邻近结点之前,可能会先深度遍历其中一个邻近结点。

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
Ford-Fulkerson 方法——最大流问题

最大流&&最小费用最大流&&最大二分匹配 Python 源码:https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow 最大流问题 比喻:有一个自来水管道运输系统,起...

廖少少
2017/09/08
0
0
图论算法 有图有代码 万字总结 向前辈致敬

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/45827145 图的定义 背景知识 看到这篇博客相信一开始映入读者眼...

nomasp
2015/05/18
0
0
Kosaraju算法的分析和证明

Kosaraju算法是求解有向图强连通分量(strong connected component)的三个著名算法之一,能在线性时间求解出一个图的强分量。用Sedgewick爷爷的话说,就是“现代算法设计的胜利”。 什么是强...

liangtee
2013/03/30
0
0
图算法系列之最短路算法Dijkstra(Java)

引言 假如你有一张地图,地图上给出了每一对相邻城市的距离,从一个地点到另外一个地点,如何找到一条最短的路? 最短路算法要解决的就是这类问题。今年的华为精英挑战赛codeCraft中关于部署...

临江仙卜算子
07/06
0
0
动态联通性问题--union-find算法

连通性问题 在给定的一张节点网络(也就是图)中,判断两个节点之是否可达的问题就是连通性问题。 场景:判断两个用户之间是否存在间接社交关系;判断两台计算机之间是否建立连接等。 定义数...

akane_oimo
2017/12/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 识别慢性能的宏

Page Profiling 给你了有关页面在载入的时候操作缓慢的邪教,你可以将下面的内容添加到调试(debug)级别: Version 3.1 及其后续版本 设置包名字为 com.atlassian.renderer.v2.components.M...

honeymose
8分钟前
0
0
day93-20180920-英语流利阅读-待学习

时尚之觞:外表光鲜靓丽,其实穷得要命 Lala 2018-09-20 1.今日导读 讲到时尚界,我们脑海里浮现的可能都是模特和设计师光鲜靓丽、从容潇洒的模样。可是,最近在法国出版的一本书却颠覆了我们...

飞鱼说编程
23分钟前
0
0
maven的pom.xml用解决版本问题

maven管理库依赖,有个好处就是连同库的依赖的全部jar文件一起下载,免去手工添加的麻烦,但同时也带来了同一个jar会被下载了不同版本的问题,好在pom的配置里面允许用<exclusion>来排除一些...

JAVA码猿
47分钟前
1
0
20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
40
9

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部