您的位置首页百科问答

连通分量是什么意思

无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。

作为遍历图并缓的应用举例,下面我们来讨论如何求图的连通分量。无向图中的极大绝雹模连通子图称为连通分量。求图的连通分量的目的,是为了确定从图中的一个顶点是否能到达图中的另一个顶点,也就是说,图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案,然而,一旦把图存入计算机中,答案就不大清楚了。

连通分量是什么意思

无向图的连通分量

无向图的G的极大连通子图称为G的连通分量(Connected)。任何连通图的连通分量都只有一个,即使是其本身,非连通的无向图有多个连通分量。

使用广度优先搜索或深度优先搜索来计算线性时间内图的连通分量(以图的顶点和边的数量表示)是很直接的。无论哪种情况,从某个特定顶点v开始的搜索将在返回之前找到包含v(并且不再有)的整个连接组件。

要查找图的所有连通分量,循环肆码遍历其顶点,每当循环到达一个尚未包含在先前找到的连通分量中的顶点时,开始新的宽度第一次或深度第一次搜索。