-
連通分量
鎖定
無向圖G的極大連通子圖稱為G的連通分量( Connected Component)。任何
連通圖的連通分量只有一個,即是其自身,非連通的
無向圖有多個連通分量。
- 中文名
-
連通分量
- 外文名
-
connected component
- 別 名
-
極大連通子圖
- 所屬領域
-
圖論、數據結構
- 相關概念
-
無向圖、強連通分量等
- 定 義
-
無向圖的極大連通子圖稱為的連通分量( Connected Component)。任何連通圖的連通分量只有一個,即是其自身,非連通的無向圖有多個連通分量
連通分量定義
無向圖的極大連通子圖稱為
的
連通分量( Connected Component)。任何
連通圖的連通分量只有一個,即是其自身,非連通的
無向圖有多個連通分量。
[1]
連通分量相關概念
路徑
①無向圖的
路徑:在
無向圖中,若存在一個頂點序列
使得
均屬於
,則稱頂點
到
存在一條路徑(Path)。
②
有向圖的路徑:在有向圖
中,路徑也是有向的,它由
中的有向邊
組成。
③路徑長度:路徑長度定義為該路徑上邊的數目。
[1]
頂點間的連通性
在無向圖
中,若從頂點
到頂點
有路徑(當然從
到
也一定有路徑),則稱
和
是連通的。
連通圖
若
中任意兩個不同的頂點
和
都連通(即有路徑),則稱
為
連通圖(Connected Graph)。例如,圖
2是連通圖。
強連通圖
有向圖
中,若對於
中任意兩個不同的頂點
和
,都存在從
到
以及從
到
的路徑,則稱
是
強連通圖。
強連通分量
有向圖的極大強連通子圖稱為
的強連通分量,強連通圖只有一個強連通分量,即是其自身。非強連通的有向圖有多個
強連通分量。
[1]
連通分量無向圖簡介
作為遍歷圖的應用舉例,下面我們來討論如何求圖的連通分量。無向圖中的極大連通子圖稱為連通分量。求圖的連通分量的目的,是為了確定從圖中的一個頂點是否能到達圖中的另一個頂點,也就是説,圖中任意兩個頂點之間是否有路徑可達。這個問題從圖上可以直觀地看出答案,然而,一旦把圖存入計算機中,答案就不大清楚了。
對於
連通圖,從圖中任一頂點出發遍歷圖,可以訪問到圖的所有頂點,即連通圖中任意兩頂點間都是有路徑可達的。
對於非連通圖,從圖中某個頂點
出發遍歷圖,只能訪問到包含頂點
的那個連通分量中的所有頂點,而訪問不到別的連通分量中的頂點。這就是説,在連通分量中的任意一對頂點之間都有路徑,但是如果
和
分別處於圖的不同連通分量之中,則圖中就沒有從
到
的路徑,即從
不可達
。因此,只要求出圖的所有連通分量,就可以知道圖中任意兩頂點之間是否有路徑可達。
[2]
- 參考資料
-
-
1.
張選芳,李廷元,付茂洺主編,何元清,王欣,高大鵬等副主編.軟件技術基礎:中國鐵道出版社,2013.08
-
2.
齊景嘉,王夢菊.數據結構(C語言描述)(第2版):清華大學出版社,2015.09