文档章节

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

一贱书生
 一贱书生
发布于 2016/11/17 13:42
字数 334
阅读 14
收藏 0
点赞 0
评论 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
博文 722
码字总数 600072
作品 0
Ford-Fulkerson 方法——最大流问题

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

廖少少 ⋅ 2017/09/08 ⋅ 0

Kosaraju算法的分析和证明

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

liangtee ⋅ 2013/03/30 ⋅ 0

HAWQ + MADlib 玩转数据挖掘之(十)——图算法之单源最短路径

一、图算法简介 1. 定义 在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一点开始,连结相关线段上的点,连线与表示...

wzy0623 ⋅ 2017/08/17 ⋅ 0

数据结构与算法面试题80道

1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 16 转换成...

_子墨 ⋅ 2014/10/22 ⋅ 0

Floyd-Warshall 全源最短路径算法

前言 全源最短路径是相对单源最短路径而言的,用于查找图中所有点对其它点的最短路径。 Floyd-Warshall算法适用于存在负权重但不存在负回路的图,稠密图,它的运行时间为O(n3)。 它的实质是动...

某昆 ⋅ 2017/12/15 ⋅ 0

【算法系列 五】 树和图

二叉搜索树的后序遍历序列(九度1367) 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 与此题相...

Hosee ⋅ 2016/08/08 ⋅ 0

四道微软面试经典算法题

比较经典的四个算法题,目前只收集到相关的思路和个别题目的解法,不断更新中 1.一个整数数列,元素取值可能是0~65535中的任意一个数,相同数值不会重复出现。0是例外,可以反复出现。 请设计...

zting科技 ⋅ 2017/11/08 ⋅ 0

MADlib——基于SQL的数据挖掘解决方案(28)——图算法之单源最短路径

图算法指利用特制的线条算图求得答案的一种简便算法。无向图、有向图和网络能运用很多常用的图算法,其中主要包括各种遍历算法(这些遍历类似于树的遍历),寻找最短路径的算法,寻找网络中最...

wzy0623 ⋅ 03/15 ⋅ 0

微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai ⋅ 2012/08/05 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 45分钟前 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

MVC——统一报文格式的异常处理响应

在我们写controller层的时候,常常会有这样的困惑,如果需要返回一个数据是,可能为了统一回去构造一个类似下列的数据格式: { status:true, msg:"保存成功!", data:[]} 而且在写...

alexzhu592 ⋅ 昨天 ⋅ 0

[知乎]SSH框架

网上图书馆管理系统包括管理员管理和图书管理,图书借阅,查询模块等等,网上商城包括前台页面和后台管理页面,两个都是以前别人的实际项目,只是别人用的不是SSH,我把他们改用SSH了,除了S...

颖伙虫 ⋅ 昨天 ⋅ 0

android -------- 打开本地浏览器或指定浏览器加载,打电话,打开第三方app

开发中常常有打开本地浏览器加载url或者指定浏览器加载, 还有打开第三方app, 如 打开高德地图 百度地图等 在Android程序中我们可以通过发送隐式Intent来启动系统默认的浏览器。 如果手机本身...

切切歆语 ⋅ 昨天 ⋅ 0

linux 安装docker

通过以下命令下载安装docker wget -qO- https://get.docker.com | sh 执行以上命令后输出以下内容说明安装成功,注意红框中的内容,docker安装成功后默认只有root能使用,红框中给出的提示是...

haoyuehong ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部