在一个有向图中,若存在一个顶点v,从该顶点有路径可以到达图中 其它所有顶点,则称此有向图为有根图,v称作图的根。 在无向图G中,若从顶点v到顶点v有路径(当然从v到v也一定有路 径),则称v和v是连通的。若VG中任意两个不同的顶点v和y都 连通即有路径),则称G为连通图 Connected Graph)。例如,图G2 和G3是连通图。 无向图G的极大连通子图称为G的连通分量 (connected Component)。 显然,任何连通图的连通分量只有一个,即是其自身,而非连通 的无向图有多个连通分量。例如,图7-4中的G4是非连通图,它有 两个连通分量H和H2 在有向图G中,若对于v(G中任意两个不同的顶点v和v,都存在 从v到v以及从v到v的路径,则称G是强连通图。有向图G的极大 强连通子图称为G的强连通分量。显然,强连通图只有一个强连 通分量,即是其自身。非强连通的有向图有多个强连通分量。例 如图7-1中的G不是强连通图,因为v到v2没有路径,但它有两个 强连通分量在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中 其它所有顶点，则称此有向图为有根图，v称作图的根。 在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路 径)，则称vi和vj是连通的。若V(G)中任意两个不同的顶点vi和vj都 连通(即有路径)，则称G为连通图(Connected Graph)。例如，图G2 和G3是连通图。 无向图G的极大连通子图称为G的连通分量(connected Component)。 显然，任何连通图的连通分量只有一个，即是其自身，而非连通 的无向图有多个连通分量。例如，图7-4中的G4是非连通图，它有 两个连通分量Hl和H2。 在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在 从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图G的极大 强连通子图称为G的强连通分量。显然，强连通图只有一个强连 通分量，即是其自身。非强连通的有向图有多个强连通分量。例 如图7-1中的Gl不是强连通图，因为v3到v2没有路径，但它有两个 强连通分量