強連通分量演算法

『壹』 請問數據結構中圖的強連通分量是什麼能具體解釋一下嗎

有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。

(1)強連通分量演算法擴展閱讀：

強連通分量Tarjan演算法

任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。

維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那麼，當前頂點就是一個強連通分量的根。

因為如果它不是強連通分量的根，那麼它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那麼存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。

至於拿出強連通分量，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。

這樣，由於當前節點是這個強連通分量中最先被壓入堆棧的，那麼在當前節點以後壓入堆棧的並且仍在堆棧中的節點都屬於這個強連通分量。

可以用反證法證明這個做法的正確性。假設一個節點在當前節點壓入堆棧以後壓入並且還存在，同時它不屬於該強連通分量，那麼它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。

『貳』 tarjan演算法詳解--關於圖的連通性 & 連通分量

Tarjan演算法關於圖的連通性和連通分量的詳解如下：

有向圖的強連通分量： 定義：在有向圖中，如果存在一個子圖，該子圖中的任意兩點間都存在雙向可達路徑，並且這個子圖不能再擴大，則稱這個子圖為強連通分量。典型的例子是環。 時間戳和追溯值：在深度優先搜索過程中，為每個節點分配一個首次訪問時間戳dfn，以及一個用於追蹤子樹中最早訪問節點的low值。 計算方法：使用棧記錄DFS路徑，通過深度優先遍歷更新low值。當發現某個節點的low值大於或等於其父節點的dfn值時，說明形成了一個強連通分量。

無向圖的割點與橋： 割點：在無向圖中，如果刪除某個點後，圖被分割成兩個或更多個連通子圖，則該點被稱為割點。 橋：在無向圖中，如果刪除某條邊後，圖被分割成兩個或更多個連通子圖，則該邊被稱為橋。 判定橋：通過比較節點的dfn值和其子節點的low值來判斷。如果邊滿足dfn[x] < low[y]，則說明沒有其他路徑可以從y到達x之前的節點，因此邊是橋。

無向圖的雙連通分量： 點雙連通分量：無割點的無向圖中，極大且任意兩點都在某個環中的連通子圖。如果圖中只有一個孤立點，它也構成一個點雙連通分量。 邊雙連通分量：無橋的連通塊，即每個連通塊都是一個邊雙連通分量。

Tarjan演算法通過深度優先搜索和棧等數據結構，高效地計算圖的連通性和連通分量，對於理解圖的結構和優化問題求解具有重要意義。