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