文档章节

数据结构-图的遍历

如比如比
 如比如比
发布于 2015/06/21 08:55
字数 866
阅读 323
收藏 10

图的遍历(Graph Traversal)是从一个顶点出发,访问且仅一次访问图中其余所有顶点,不是所有边的处理。是求图的连通性,拓扑排序,路径求解等问题的基础。

非常基本的图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。

 

深度优先搜索,Depth First SearchDFS

深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问,依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w,从w出发按同样的方法向前遍历,直到图中所有顶点都被访问。属于盲目搜索。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。

因发明“深度优先搜索算法”,霍普克洛夫特与罗伯特·塔扬共同获得计算机领域的最高奖:图灵奖.

 

广度优先搜索,Breadth First SearchBFS

图的广度优先搜索是树的按层次遍历的推广,是连通图的一种遍历策略。因为它的思想是从一个顶点vi开始,辐射状地优先遍历其周围较广的区域,故而得名。它的基本思想是:首先访问初始点vi,并将其标记为已访问过,接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t,并均标记已访问过,然后再按照vi1,vi2,…, vi t的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

广度先搜索的实现一般采用open-closed表。

BFS是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)

一个最直观经典的应用例子是走迷宫,从起点开始,找出到终点的最短路程,很多最短路径算法就是基于广度优先的思想成立的。


© 著作权归作者所有

如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
加载中

评论(1)

眹希
眹希
几种数据存储结构详解

影响空间规模的几种数据存储结构 正文 所谓数据存储结构,就是数据的元素与元素之间在计算机中的一种表示,它的目的是为了解决空间规模问题,或者是通过空间规模问题从而间接地解决时间规模问...

长平狐
2012/11/12
795
1
数据结构之图(存储结构、遍历)

  新学期开始了,开始专心于技术上了,上学期的寒假总是那么短暂,飘飘乎就这样逝去,今天补补上学期还没学完的数据结构---图,希望能和大家一起探讨,共同进步~ 定义:   图是由顶点集合...

graylee
2015/03/10
0
0
数据结构第12讲 二叉树的层次遍历

数据结构第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示: ...

rainchxy
2017/11/14
0
0
图的JS实现

图的定义 图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明,例如人际关系,或者地图。 其中图还分为有向图和无向图。 如下就是有向图 图的数据结构 对于图这种关系,可...

光哥很霸气
2017/10/12
0
0
用js来实现那些数据结构16(图02-图的遍历)

  上一篇文章我们简单介绍了一下什么是图,以及用JS来实现一个可以添加顶点和边的图。按照惯例,任何数据结构都不可或缺的一个point就是遍历。也就是获取到数据结构中的所有元素。那么图当...

zaking
2018/05/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 磁盘不足异常

linux 报 No space left on device 异常 ,则是磁盘不足 ,导致异常 运行 df -h 命令查询磁盘使用率,如果有100%,则查找目录大日志文件删除 1.磁盘不足导致系统应用写入文件失败,如系统日志...

zaolonglei
36分钟前
3
0
即学即用的 30 段 Python 实用代码

☞ 分享:最全最新的Python学习大礼包 ☜ 点击查看 编译:Pita & AI开发者,作者:Fatos Morina Python是目前最流行的语言之一,它在数据科学、机器学习、web开发、脚本编写、自动化方面被许...

Object_Man
37分钟前
4
0
The server time zone value 'EDT' is unrecognized or represents more than one time zone.

2019-10-14 18:07:43.714 ERROR 74363 --- [Druid-ConnectionPool-Create-1855026648] com.alibaba.druid.pool.DruidDataSource : create connection SQLException, url: jdbc:mysql://10.30......

yizhichao
50分钟前
8
0
html加载顺序以及影响页面二次渲染额的因素

本文转载于:专业的前端网站➱html加载顺序以及影响页面二次渲染额的因素 浏览器请求发往服务器以后,返回HTML页面,页面内容开始渲染,具体的执行顺序为: 1. 浏览器开始载入html代码,发现<...

前端老手
52分钟前
9
0
BeginnersBook JSP、JSTL、Servlet 教程

来源:ApacheCN BeginnersBook 翻译项目 译者:飞龙 协议:CC BY-NC-SA 4.0 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 请您勇敢地去翻译和改进翻译。虽然我们追求卓越,但我们并...

ApacheCN_飞龙
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部