给定有向图,设计一个算法,找出两个结点之间是否存在一条路径
给定有向图,设计一个算法,找出两个结点之间是否存在一条路径
一贱书生 发表于1年前
给定有向图,设计一个算法,找出两个结点之间是否存在一条路径
  • 发表于 1年前
  • 阅读 14
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

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

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

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

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

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

 

[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.     }  

 

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

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 17
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: