前面介绍了《图存储结构》,本节继续讲解什么是连通图。
前面讲过,图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图1中,虽然v1和v3没有直接关联,但从v1到v3存在两条路径,分别是 v1-v2-v3 和 v1-v4-v3,因此称v1和v3之间是连通的。
图1顶点之间的连通状态示意图
无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。例如,图2中的无向图就是一个连通图,因为此图中任意两顶点之间都是连通的。
图2连通图示意图
若无向图不是连通图,但图中存储某个子图符合连通图的性质,则称该子图为连通分量。
前面讲过,由图中部分顶点和边构成的图为该图的一个子图,但这里的子图指的是图中"最大"的连通子图(也称"极大连通子图")。
如图3所示,虽然图3a)中的无向图不是连通图,但可以将其分解为3个"最大子图"(图3b)),它们都满足连通图的性质,因此都是连通分量。
图3连通分量示意图提示,图3a)中的无向图只能分解为3部分各自连通的"最大子图"。
需要注意的是,连通分量的提出是以