无向图G的极大连通子图称为G的连通分量( Connected Component)。任何
连通图的连通分量只有一个,即是其自身,非连通的
无向图有多个连通分量。
无向图的极大连通子图称为的连通分量( Connected Component)。任何
连通图的连通分量只有一个,即是其自身,非连通的
无向图有多个连通分量。
①无向图的
路径:在
无向图中,若存在一个顶点序列 使得 均属于 ,则称顶点 到 存在一条路径(Path)。
②
有向图的路径:在有向图中,路径也是有向的,它由 中的有向边 组成。
若中任意两个不同的顶点 和 都连通(即有路径),则称为
连通图(Connected Graph)。例如,图2是连通图。
有向图中,若对于中任意两个不同的顶点 和 ,都存在从 到 以及从 到 的路径,则称是
强连通图。
有向图的极大强连通子图称为的强连通分量,强连通图只有一个强连通分量,即是其自身。非强连通的有向图有多个
强连通分量。
作为遍历图的应用举例,下面我们来讨论如何求图的连通分量。无向图中的极大连通子图称为连通分量。求图的连通分量的目的,是为了确定从图中的一个顶点是否能到达图中的另一个顶点,也就是说,图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案,然而,一旦把图存入计算机中,答案就不大清楚了。
对于
连通图,从图中任一顶点出发遍历图,可以访问到图的所有顶点,即连通图中任意两顶点间都是有路径可达的。
对于非连通图,从图中某个顶点 出发遍历图,只能访问到包含顶点 的那个连通分量中的所有顶点,而访问不到别的连通分量中的顶点。这就是说,在连通分量中的任意一对顶点之间都有路径,但是如果 和 分别处于图的不同连通分量之中,则图中就没有从 到 的路径,即从 不可达 。因此,只要求出图的所有连通分量,就可以知道图中任意两顶点之间是否有路径可达。