5.3.3 图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。

对于无向图来说,如果无向图是连通的,则从任一结点出发,仅需一次遍历就能够访问图中所有顶点;

如果无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点无法通过这次遍历访问。

对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问图中的所有顶点,否则不能访问到所有顶点。

故而在BFSTraverse()和DFSTraverse()中添加了第二个for循环,再选取初始点,继续进行遍历,以防止一次无法遍历图中所有顶点。

对于无向图,上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于图中的连通分量树;

而对于有向图,则不是这样没因为一个连通的有向图分为强连通的和非强连通的,它的连通子图也分为强连通分量和非强连通分量,非强连通分量一次调用BFS(G,i)或DFS(G,i)无法访问到该连通分量的所有顶点。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LhWorld哥陪你聊算法

Hadoop源码篇--Reduce篇

Reduce文件会从Mapper任务中拉取很多小文件,小文件内部有序,但是整体是没序的,Reduce会合并小文件,然后套个归并算法,变成一个整体有序的文件。

28210
来自专栏伪君子的梦呓

题解 ~ 输出所有的水仙花数

打印所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该本身。 例如:153 是一个水仙花数,因为

18930
来自专栏C语言及其他语言

优秀题解【图的遍历——深度优先搜索】

解题思路: (1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

9520
来自专栏函数式编程语言及工具

PICE(5):MongoDBStreaming - gRPC -MGO Service

  我在前面提到过MongoDB不支持像SQL般字符式的操作指令,所以我们必须对所有的MongoDB操作指令建立protobuf类型才能支持MongoDB指令的...

14640
来自专栏码匠的流水账

聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

9110
来自专栏张俊红

数据结构-图

图是不同于前面两种数据结构的另一种新的数据结构,线性表中元素与元素之间是被串起来的,每个数据元素只有一个直接前驱和一个直接后继,是一种一对一的数据结构;在树的结...

39610
来自专栏十月梦想

JavaScript一维数组遍历

通过for循环获取数组的下标循环输出数组,和php的遍历类似,这里for循环遍历一维数组

11320
来自专栏张善友的专栏

如何去理解 拓扑排序算法

查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:        对于一条有向边(u,v),定义u < v;满足所...

249100
来自专栏李家的小酒馆

图论基本知识

图 图的基本概念 图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。 ? 图分为有向图和无向图,无向图为两个节点之间互相可以到达...

21800
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。 * Modify homegarden data set with ass...

48240

扫码关注云+社区

领取腾讯云代金券