【安利Java零基础】图连通性连通图的基本性质

目录

关于作者：大家好！我是路遥夜夜，你可以叫我夜夜！ ❣️

个人主页：【陆耀野的博客】

博主资讯：四季轮流落叶，一路招摇！

列

【安利Java零基础】

【数据结构-Java语言描述】

希望大家多多支持，共同进步！ ~❤️

如果有帮助，请[关注➕点赞➕收藏]c语言无向图连通分量，如果没有，我会更加努力！

——————————————————

如果你想寻找可以一起成长的小伙伴，请点击【Java全栈开发社区】

前言对连通图的理解

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

在无向图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. 但是你要知道最小连通子图只存在于连通无向图中，不存在于不连通无向图和有向图中。

无向图中的最大连通子图

无向图中的最大连通子图也称为连通分量。

无向图可以分为两种：连通无向图和不连通无向图。

最小连通子图

最小连通子图只存在于连通无向图中，即图中只有一个连通分量（最大连通子图）。之所以说极小，是因为最小连通子图只要求包含图中所有的顶点和比顶点数少一的边（并且不能形成环），即也就是说，如果在最小连通子图中的任意两个顶点之间添加一条边c语言无向图连通分量，则一定有一个循环。

这里的最大值和最小值不是同一个意思。不要混淆他们。最大连通子图是连通分量，最小连通子图是生成树。

我们来几个图例，让大家深入了解一下连通组件：

如图3所示，图a中的无向图虽然不是连通图，但可以分解为3个“最大子图”（图b），它们都满足连通图的性质，所以都是连接组件。

看了这么多传说，你学会了吗？你能在图中找到连通分量吗？

需要注意的是，连通分量的提出是基于“整个无向图不是连通图”的前提，因为如果无向图是连通图，它不能分解成多个最大连通子图，因为图中所有的顶点都是连通的。

三、强连通图

1. 如果一个有向图 G 对于其中的任意两个顶点 v 和 u 有一条从 v 到 u 和从 u 到 v 的有向路径，则 G 称为强连通图。在一个不是强连通图的有向图 G 中，如果两个顶点 u 和 v 在两个方向上都有有向路径，则称 u 和 v 是强连通的。

2. 强连通图：在有向图中，如果任意两个顶点相连（有向路径），则该图称为强连通图。

3. 在有向图中，如果任意两个顶点 Vi 和 Vj 从 Vi 到 Vj 和从 Vj 到 Vi 相连，即它们都包含至少一条路径，则称有图是强连接的。如图4所示，是一个强连通图。

四、强连通分量

1. 在有向图中，如果从任意顶点出发，通过图中的边可以到达图中的每一个顶点，称为强连通图。有向图中顶点数最多的强连通子图称为强连通分量。

2.和有向图G的极强连通子图S，即添加任意顶点都会使S失去强连通性的性质，则称S为G的强连通分量。

3. 强连通分量：有向图中的最大强连通子图。强连通图本身只有一个强连通分量。

4. 同时，如果有向图本身不是强连通图，但它所包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。虽然整个有向图不是强连通图，但它包含两个强连通分量。

“强强”在哪里——连通图和强连通图的区别？

可以说，连通图是在无向图的基础上，对图中顶点之间的连通性提出了更高的要求，而强连通图是在有向图。提出了更高的要求。

写到最后❣️四季轮回，已经数不清有多少叶子枯萎了❣️未来愿我们随心而行，一路赢！您的支持和认可是我创作的动力。创建起来并不容易。你可能会喜欢它并评论❤️保存它。谢谢大家的支持，也欢迎大家来给我一些建议。想知道更多？没时间解释了，加油！

路遥野的博客_CSDN博客-数据结构，安利Java零基础，spring领域博主