連通分量（connected components）

想像一張由橋相連的島嶼地圖。有些島連成一塊你能不沾濕腳就走遍的陸地；其他的則自成孤島。無向圖的一個連通分量就是這樣一個可達的群集：一個極大的頂點集合，其中任一頂點都能沿邊走到任一其他頂點。「極大」意味你無法再加入另一個頂點還保持連通——每個分量都是一塊完整、自成一體的部分，而整張圖是這些部分的不相交堆疊。

找出它們是圖搜尋最乾淨的用途。把每個頂點標記為未拜訪；然後對每個仍未拜訪的頂點，從它發起一趟全新的 BFS 或 DFS，向外淹沒並標記所有可達者，把它們全都貼上同一個分量編號；遞增編號並重複，直到沒有未拜訪的頂點。發起的趟數就是連通分量的數目。為何每次淹沒恰是一個分量？因為從 v 出發的走訪恰好抵達所有與 v 連通的頂點（這就是無向圖中可達的意思），而它恰好停在沒有邊跨越的邊界——所以它捕捉的是一個極大連通集，不多也不少。整趟下來每個頂點被拜訪一次、每條邊被檢視一次，故總成本是 O(n + m)。

連通分量回答「這個網路分成幾塊獨立的部分、哪些頂點共享一塊？」——用於分群、影像分割（相鄰且同色的像素）、檢查網路是否完全連通，以及許多演算法之前的前處理步驟。兩個誠實的提醒。第一，這個概念是給無向圖的；有向圖需要更微妙的強連通分量概念，因為在有向圖中你可能能從 u 抵達 v 卻無法從 v 抵達 u。第二，一個增量式的表親——並查集（互斥集）結構——能在邊一條條加入時維護分量，這正是克魯斯卡最小生成樹演算法所倚賴的——但對靜態圖而言，單一趟線性走訪是最簡單的正確工具。