分量演算法

1. tarjan演算法詳解--關於圖的連通性 & 連通分量

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

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

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

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

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