【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强，强强在哪里？

前言

对连通图的理解

在图论中，连通图基于连通的概念。

在一个 无向图G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称i和j是连通的。

如果 G 是有向图，那么连接 i 和 j 的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图连通性的是图的基本性质。

一、什么是连通图？

连通：在无向图中，若从顶点u到顶点v有路径，则称u和v是连通的。

图中从⼀个顶点到达另⼀顶点，若存在⾄少⼀条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强，强强在哪里？

二、什么是连通分量？

若⽆向图不是连通图，但图中存储某个⼦图符合连通图的性质，则称该⼦图为连通分量。
由图中部分顶点和边构成的图为该图的⼀个⼦图，但这⾥的⼦图指的是图中”最⼤”的连通⼦图（也称”极⼤连通⼦图”）。

若无向图为非连通图，则图中各个极大连通子图称为此图的连通分量。

2.1 、那什么是极大连通子图呢？联想到的极小连通子图又是什么呢？

1. 首先先明确两个概念，无向图和有向图；其次，明确一个概念极大连通子图，可以存在于无向图中,也可以存在于有向图中；

2. 但要知道，极小连通子图只存在于连通的无向图中，不存在于不连通的无向图和有向图中。

也就是说，极大连通子图和极小连通子图适用条件是不一样的，尽管它们看起来貌似很接近。

无向图中的极大连通子图

无向图中的极大连通子图也叫连通分量。

无向图可以分成两种类型：连通的无向图、不连通的无向图。

连通的无向图只有一个极大连通子图，即它本身，因为不存在另一个连通的子图包含的点和边比它本身还要多，所以叫作极大连通子图。

不连通的无向图可以拆分为若干个连通的无向图，如果我们在拆分时注意把能连通的点边都放在一个连通子图中，使这个连通子图足够大，以至于再多包含一个点或边它就变成不连通的了，我们称这个连通子图为极大连通子图，也叫连通分量。

极小连通子图

极小连通子图只存在于连通的无向图中，也就是说该图中只有一个连通分量（极大连通子图），之所以说它极小，是因为极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边（且不能成环），也就是说如果给极小连通子图任意两个顶点间加入一条边,则必有环。