1. 引言在圖論中點雙連通分量Biconnected Components簡稱 BCC是一個重要的概念用于描述無向圖中“連通性”更強的子結(jié)構(gòu)。理解點雙連通分量對于分析網(wǎng)絡(luò)可靠性、設(shè)計容錯系統(tǒng)以及解決某些圖論問題如尋找割點至關(guān)重要。簡單來說一個點雙連通圖是指一個沒有割點Articulation Point的連通無向圖。而一個圖的點雙連通分量則是其極大的點雙連通子圖。2. 核心概念2.1 割點Articulation Point在一個連通無向圖中如果移除某個頂點及其關(guān)聯(lián)的邊后圖不再連通那么這個頂點就被稱為割點。示例1 — 2 — 3 | 4在上圖中頂點 2 是一個割點。因為移除頂點 2 后圖會分裂成兩個連通部分{1} 和 {3, 4}。2.2 點雙連通圖Biconnected Graph一個連通無向圖是點雙連通的當(dāng)且僅當(dāng)它不包含任何割點。這意味著圖中任意兩個頂點之間至少存在兩條點不重復(fù)的路徑。性質(zhì)點雙連通圖具有更強的“魯棒性”。移除任何一個頂點圖仍然保持連通。一個點雙連通分量是原圖的一個極大點雙連通子圖即無法通過添加更多的邊和頂點來自原圖而保持點雙連通性。3. 算法Tarjan 算法求點雙連通分量最經(jīng)典的算法是基于深度優(yōu)先搜索DFS的 Tarjan 算法。該算法在 O(VE) 的時間復(fù)雜度內(nèi)可以同時求出圖中的所有割點和點雙連通分量。3.1 算法思路DFS 序dfn記錄每個頂點在 DFS 中被訪問的順序時間戳。追溯值low記錄每個頂點通過其子孫頂點或一條回邊back edge所能到達的最早祖先的 dfn 值。棧stack用于在 DFS 過程中存儲邊或頂點以便在發(fā)現(xiàn)一個完整的點雙連通分量時可以將其彈出。3.2 判斷割點的條件對于 DFS 樹中的非根節(jié)點 u如果存在一個子節(jié)點 v滿足low[v] dfn[u]則 u 是一個割點。這意味著 v 及其子孫無法通過回邊到達 u 的祖先移除 u 后v 所在的子樹將與圖的其余部分分離。對于根節(jié)點如果它有兩個或更多子節(jié)點則它是一個割點。3.3 求點雙連通分量的過程從任意頂點開始 DFS。將遍歷到的邊壓入棧。當(dāng)發(fā)現(xiàn)一個頂點 u 滿足割點條件即對于某個子節(jié)點 v有l(wèi)ow[v] dfn[u]時從棧中不斷彈出邊直到彈出邊 (u, v) 為止。這些彈出的邊以及它們關(guān)聯(lián)的頂點構(gòu)成一個點雙連通分量。注意一個割點可能屬于多個點雙連通分量。4. 代碼實現(xiàn)C#include iostream #include vector #include stack #include algorithm using namespace std; const int MAXN 10005; vectorint graph[MAXN]; int dfn[MAXN], low[MAXN], timestamp 0; stackpairint, int stk; // 存儲邊的棧 vectorvectorint bccs; // 存儲所有點雙連通分量用頂點集表示 void dfs(int u, int parent) { dfn[u] low[u] timestamp; int childCount 0; for (int v : graph[u]) { if (v parent) continue; // 避免走回父邊 if (!dfn[v]) { // v 未被訪問是樹邊 stk.push({u, v}); childCount; dfs(v, u); low[u] min(low[u], low[v]); // 判斷 u 是否為割點并提取點雙連通分量 if (low[v] dfn[u]) { vectorint component; pairint, int edge; do { edge stk.top(); stk.pop(); // 將邊的兩個端點加入分量去重 if (find(component.begin(), component.end(), edge.first) component.end()) component.push_back(edge.first); if (find(component.begin(), component.end(), edge.second) component.end()) component.push_back(edge.second); } while (!(edge.first u edge.second v)); bccs.push_back(component); } } else if (dfn[v] dfn[u]) { // v 已被訪問且不是父節(jié)點是回邊 low[u] min(low[u], dfn[v]); stk.push({u, v}); // 回邊也需要壓棧 } } // 根節(jié)點特殊判斷如果 childCount 2則根是割點 // (但根節(jié)點的割點判斷不影響點雙連通分量的提取邏輯) } void findBCCs(int n) { for (int i 1; i n; i) { if (!dfn[i]) { dfs(i, -1); } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); } findBCCs(n); cout 點雙連通分量數(shù)量: bccs.size() endl; for (int i 0; i bccs.size(); i) { cout 分量 i 1 : ; for (int v : bccs[i]) { cout v ; } cout endl; } return 0; }5. 應(yīng)用場景網(wǎng)絡(luò)可靠性分析識別通信網(wǎng)絡(luò)或電路中的關(guān)鍵節(jié)點割點。加固這些節(jié)點可以提升整個網(wǎng)絡(luò)的容錯能力。圖的可平面性判定某些圖的可平面性測試需要基于點雙連通分量進行。解決某些圖論問題如“在圖中添加最少的邊使其變?yōu)辄c雙連通圖”等。社交網(wǎng)絡(luò)分析識別社區(qū)結(jié)構(gòu)中連接不同群體的關(guān)鍵人物。6. 點雙連通分量 vs. 邊雙連通分量為了更清晰地理解這里對比一下點雙連通分量BCC和邊雙連通分量Edge-Biconnected Component, EBCC特性點雙連通分量 (BCC)邊雙連通分量 (EBCC)定義極大無割點子圖極大無橋割邊子圖關(guān)注點頂點邊重疊割點屬于多個 BCC頂點屬于唯一 EBCC關(guān)系兩個 EBCC 至多通過一個割點相連將每個 BCC 縮點后得到一棵“塊-割點樹”7. 總結(jié)點雙連通分量是分析無向圖連通性強度的核心工具。通過 Tarjan 算法我們可以在線性時間內(nèi)高效地找出所有割點和點雙連通分量。掌握這一概念和算法對于解決涉及圖結(jié)構(gòu)魯棒性、關(guān)鍵節(jié)點識別等實際問題具有重要意義。學(xué)習(xí)建議在理解算法思想后動手實現(xiàn)代碼并用不同的圖進行測試觀察割點和點雙連通分量的輸出以加深理解。