[algorithms] Advanced Graph 進階圖論

cover

視覺化概覽

flowchart TD
    A["Prim MST 演算法"] --> B["選擇起始節點\n加入 MST 集合"]
    B --> C["將鄰邊加入\n優先佇列 PQ"]
    C --> D{"PQ 非空？"}
    D -- 是 --> E["取出權重最小的邊\n(u, v, w)"]
    E --> F{"v 已在 MST？"}
    F -- 是 --> D
    F -- 否 --> G["將 v 加入 MST\n記錄邊 (u,v)"]
    G --> H["將 v 的鄰邊\n加入 PQ"]
    H --> D
    D -- 否 --> I["MST 建構完成"]

最小生成樹 MST

Prim vs Kruskal

演算法	適用	時間複雜度
Prim	稠密圖	O(E log V)
Kruskal	稀疏圖	O(E log E)

Prim 演算法

從一個點開始，每次加入最近的點

PriorityQueue<int[]> pq;  // (權重, 節點)
pq.add({0, 0});           // 從節點 0 開始
 
while (!pq.isEmpty()) {
    取出權重最小的節點 u;
    if (已在 MST) continue;
    加入 MST;
    對於每個鄰居 v:
        if (邊權重 < 到 v 的最小權重)
            更新並加入 pq;
}

Kruskal 演算法

按邊權重排序，依序加入不形成環的邊

用 Union-Find 判斷是否形成環。

強連通分量 SCC

有向圖中，任意兩點可以互達的最大子圖

    ┌─→ 1 ─→ 2 ─┐
    │    ↖    ↓  │
    0      ↖─────┘
    │
    └─→ 3 ─→ 4

SCC: {0,1,2}, {3}, {4}

Tarjan 演算法

一次 DFS，維護：

dfn[u]：訪問時間
low[u]：能回到的最早祖先

dfn[u] = low[u] = time++;
stack.push(u);
 
for (v in neighbors) {
    if (!visited[v]) {
        dfs(v);
        low[u] = min(low[u], low[v]);
    } else if (onStack[v]) {
        low[u] = min(low[u], dfn[v]);
    }
}
 
if (low[u] == dfn[u]) {
    // u 是 SCC 的根
    彈出 stack 直到 u，形成一個 SCC
}

Kosaraju 演算法

兩次 DFS：

第一次：記錄完成順序
反轉圖
第二次：按逆完成順序 DFS

割點與橋

割點（Articulation Point）

移除後圖不連通的點。

橋（Bridge）

移除後圖不連通的邊。

    1 ─── 2         3 ─── 4
     \   /           \
      \ /             5
       0

節點 0 是割點
邊 0-3 是橋

判定條件

// 割點：子節點無法不經過 u 回到 u 的祖先
if (parent == -1 && children > 1) 割點  // 根節點
if (parent != -1 && low[v] >= dfn[u]) 割點
 
// 橋：v 完全無法回到 u 或之前
if (low[v] > dfn[u]) 橋

二分圖

節點可分成兩組，邊只存在於組間

  A       B
  0 ───── 1
  │       │
  2 ───── 3

判定方法

BFS/DFS 染色：相鄰節點顏色不同

boolean isBipartite() {
    for (u in graph) {
        if (!colored[u]) {
            bfs(u, color=0);
            // 如果發現相鄰同色，不是二分圖
        }
    }
}

二分圖匹配

最大匹配

找最多的邊，使每個節點最多連一條邊。

匈牙利演算法

嘗試為每個左側節點找配對：

如果右側未配對，配對
如果右側已配對，嘗試讓原配對者換人

boolean dfs(int u) {
    for (v in neighbors[u]) {
        if (!used[v]) {
            used[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

網路流（進階）

解決最大流問題，常見演算法：

Ford-Fulkerson
Edmonds-Karp
Dinic

時間複雜度總結

演算法	問題	複雜度
Prim	MST	O(E log V)
Kruskal	MST	O(E log E)
Tarjan	SCC	O(V + E)
Kosaraju	SCC	O(V + E)
割點橋	關鍵點邊	O(V + E)
二分圖判定	染色	O(V + E)
匈牙利	最大匹配	O(VE)

經典題目

最小生成樹 - LeetCode 1135
冗餘連接 II - LeetCode 685（有向圖）
課程表 II - LeetCode 210（拓撲排序）
二分圖判定 - LeetCode 785
圖的連通分量 - LeetCode 323

Terry Yao's Blog

分類

目錄