数据结构论坛

首页 » 分类 » 问答 » 数据结构强连通图的几个问题
TUhjnbcbe - 2023/9/7 21:18:00

注:强连通图说的是有向图,连通图说的是无向图,路径的意思是能到就行,其中间可以有中转站,也就是允许经过其他结点

问题一:强连通图任意两个顶点存在一条有向路径还是a到b到a都得互相有路径?

解:互相有路径,也就是顺着箭头的方向走,

既可以从a走到b,也可以从b走到a

问题二:啥是极大强连通子图?

解:1.为什么叫做极大?

极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。

2.就是能连通的一个最大的有向图

3.强连通图的极大强连通子图为其本身。(是唯一的)

问题三:还有啥是强连通分量?

解:极大强连通子图叫做强连通分量,看下边这个例子

首先要明确,

1.极大强连通子图肯定是连通的,

2.若在增加一个结点,他们所构成的图将不是连通的

3.若该有向图是强连通图,那么其极大强连通子图就是他本身

(那么其强连通分量就为一,也就是说有几个极大强连通子图就有几个强连通分量)

4.非强连通图有多个极大强连通子图

首先这个有向图不是一个强连通图

例如(D-CButC!-D)

那么它就有多个极大强连通子图

用word画的一个有向图

经过计算,你就知道它有3个极大强连通子图就等价它有3个强连通分量。

问题四:非强连通图是不是没有强连通分量?

解:非强连通图有多个极大强连通子图

注:

1
查看完整版本: 数据结构强连通图的几个问题