文档章节

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

一贱书生
 一贱书生
发布于 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

没有更多内容

加载失败,请刷新页面

加载更多

CockroachDB

百度云上的CockroachDB 云数据库 帮助文档 > 产品文档 > CockroachDB 云数据库 > 产品描述 开源NewSQL – CockroachDB在百度内部的应用与实践 嘉宾演讲视频及PPT回顾:http://suo.im/5bnORh ...

miaojiangmin
19分钟前
0
0
I2C EEPROM驱动实例分析

上篇分析了Linux Kernel中的I2C驱动框架,本篇举一个具体的I2C设备驱动(eeprom)来对I2C设备驱动有个实际的认识。 s3c24xx系列集成了一个基于I2C的eeprom设备at24cxx系列。at24cxx系列芯片包...

yepanl
20分钟前
0
0
spring mvc拦截器,实现统计http请求的后台运行时间

使用两种方式,实现拦截http请求的后台运行时间。 废话不多说直接上代码 /** * Http请求时间统计 * 拦截所有请求 */public class HttpRquestTimeInterceptor extends HandlerIntercepto...

兜兜毛毛
38分钟前
1
0
设计模式之工厂模式

本篇博文主要翻译这篇文章: https://www.journaldev.com/1392/factory-design-pattern-in-java 由于翻译水平有限,自认为许多地方翻译不恰当,欢迎各位给出宝贵的建议,建议大家去阅读原文。...

firepation
53分钟前
4
0

中国龙-扬科
56分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部