「圖」（Graph）是電腦科學中最具表達力的資料結構之一。任何牽涉到「物件」與「物件之間關係」的問題，幾乎都能用圖來建模：社群網路的朋友關係、地圖上的道路、網頁之間的超連結、程式的相依性、晶片上的線路、金融交易的金流、分子的原子鍵結……。一旦把問題抽象成圖，我們就能套用一整套成熟、強大且效率經過嚴格證明的演算法來求解。

本教材的目標，是帶你從零開始、系統性地掌握圖論演算法。我們會回答四個核心問題：

1. 如何表示圖？ —— 鄰接矩陣、鄰接串列、邊串列各自的取捨。

2. 如何走訪與分析圖？ —— BFS、DFS 與其衍生的連通性、拓撲排序、環偵測、橋與割點。

3. 如何解決經典圖問題？ —— 最短路徑（Dijkstra、Bellman-Ford、Floyd-Warshall、A*）、最小生成樹（Kruskal、Prim）、網路流與二分匹配、最近共同祖先。

4. 真實世界如何應用？ —— 導航、社群推薦、詐欺偵測、排程、編譯器、網路路由，以及現代的圖神經網路（GNN）與圖資料庫。

閱讀建議：若你是初學者，請依章節順序閱讀，先打穩第 1–3 章（表示法與走訪）的基礎；若你準備面試或競賽，可直接跳到對應主題，並搭配第 13 章「解題策略：如何辨識題型」與第 15 章的練習題。

圖論基礎與術語

理解圖論演算法的前提，是先把術語講清楚。本章建立全書共用的語彙與數學記號。

什麼是圖

頂點代表「物件」，邊代表「物件之間的關係」。例如在社群網路中，頂點是使用者，邊是「好友」關係；在地圖中，頂點是路口，邊是道路。

上圖是一個 \(n=5\)、\(m=6\) 的無向圖。

有向圖與無向圖

• 無向圖（undirected graph）：邊沒有方向，\((u,v)\) 與 \((v,u)\) 是同一條邊。例如 Facebook 的好友關係（互相的）。

• 有向圖（directed graph / digraph）：邊有方向，\((u,v)\) 表示「從 \(u\) 指向 \(v\)」。例如 Twitter 的追蹤關係、網頁超連結、工作相依性。

加權圖與無權圖

若每條邊都附帶一個數值 \(w(u,v)\)，稱為加權圖（weighted graph）。權重可表示距離、成本、時間、容量或機率。沒有權重（或視為權重皆為 1）的圖稱為無權圖（unweighted graph）。

重要術語速覽

圖的稀疏性與演算法選擇

「稀疏」還是「稠密」會直接影響你該用哪種表示法與演算法。一個直覺的判準：

\[\text{稠密} \iff m = \Theta(n^2), \qquad \text{稀疏} \iff m = O(n).\]

大多數真實世界的圖（社群網路、道路網、網頁圖）都是稀疏的——每個節點的鄰居數遠小於 \(n\)。這也是為什麼鄰接串列（第 2 章）幾乎是預設選擇。

圖的表示法

「如何在記憶體中表示一張圖」是所有圖演算法的起點。選錯表示法，輕則浪費記憶體，重則讓演算法慢上好幾個數量級。本章比較三種主流表示法。

鄰接矩陣 (Adjacency Matrix)

用一個 \(n \times n\) 的二維陣列 \(A\) 表示，其中 \[A[u][v] = \begin{cases} 1 & \text{若 } (u,v) \in E \text{（無權圖）}\\ w(u,v) & \text{若加權圖}\\ 0 \text{ 或 } \infty & \text{否則} \end{cases}\]

優點：查詢「\(u\) 與 \(v\) 是否相鄰」為 \(O(1)\)；實作簡單；適合稠密圖與需要頻繁查邊的演算法（如 Floyd-Warshall）。

缺點：空間固定為 \(O(n^2)\)，對稀疏圖極度浪費；列舉某頂點的所有鄰居需 \(O(n)\)。

int n;                                 // 頂點數
vector<vector<int>> A(n, vector<int>(n, 0));
A[u][v] = 1;                           // 加一條無向邊
A[v][u] = 1;

鄰接串列 (Adjacency List)

每個頂點維護一個「鄰居清單」。這是最常用的表示法，因為真實圖多為稀疏。

優點：空間為 \(O(n+m)\)；列舉鄰居只花 \(O(\deg(v))\)；適合稀疏圖與絕大多數走訪／最短路演算法。

缺點：查詢「\(u,v\) 是否相鄰」需 \(O(\deg(u))\)（非 \(O(1)\)）。

int n;
vector<vector<pair<int,int>>> adj(n);  // adj[u] = {(鄰居, 權重), ...}
adj[u].push_back({v, w});              // 有向邊 u -> v
adj[v].push_back({u, w});              // 無向圖再加反向

邊串列 (Edge List)

直接存所有邊 \(\{(u, v, w)\}\)。本身不利於查鄰居，但對某些演算法（Kruskal 需要把邊依權重排序、Bellman-Ford 逐邊鬆弛）反而最自然。

struct Edge { int u, v, w; };
vector<Edge> edges;
edges.push_back({u, v, w});

三種表示法的比較

隱式圖 (Implicit Graph)

很多題目不會明確給你一張圖，而是「狀態空間」本身就是圖：

• 格子地圖：每個格子是頂點，上下左右相鄰格是鄰居（牆壁除外）。

• 字串轉換（Word Ladder）：每個單字是頂點，差一個字母的單字相連。

• 棋盤狀態：每個盤面是頂點，合法走步連到下一盤面。

這類問題不需建出整張圖，只要在走訪時即時生成鄰居即可。這是 BFS/DFS 最常見的實戰形式。

圖的走訪：BFS 與 DFS

走訪（traversal）是「有系統地拜訪圖中每個頂點」的過程，是幾乎所有圖演算法的骨架。兩大基石是廣度優先搜尋（BFS）與深度優先搜尋（DFS）。

廣度優先搜尋 (BFS)

BFS 從起點出發，一層一層向外擴張：先拜訪所有距離為 1 的頂點，再拜訪距離為 2 的，依此類推。它用一個佇列（queue, FIFO）來維護「待拜訪」的頂點。

演算法流程

1. 將起點 \(s\) 放入佇列，標記 \(dist[s]=0\)，其餘為未拜訪。

2. 當佇列非空：取出隊首 \(u\)，對每個未拜訪鄰居 \(v\)，設 \(dist[v]=dist[u]+1\)，並入列。

核心性質

直覺證明：BFS 按距離遞增的順序拜訪頂點，因此第一次抵達某頂點時，必定走的是最短路。

vector<int> bfs(const vector<vector<int>>& adj, int s) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {          // 尚未拜訪
                dist[v] = dist[u] + 1;
                q.push(v);
            }
    }
    return dist;
}

複雜度：每個頂點入列／出列一次、每條邊檢查一次，故時間 \(O(V+E)\)，空間 \(O(V)\)。

BFS 的延伸應用

• 多源 BFS：把所有起點一次放入佇列（如「腐爛的橘子」、火勢蔓延）。

• 0-1 BFS：邊權只有 0 或 1 時，用雙端佇列取代優先佇列，達 \(O(V+E)\)（見第 7 章）。

• 二分圖判定：BFS 交錯著色，若發現相鄰同色則非二分圖（見第 4 章）。

深度優先搜尋 (DFS)

DFS 採取「一路走到底，再回頭」的策略：從某頂點出發，盡量往深處探索，直到無路可走才回溯。它天然以遞迴（或顯式堆疊）實作。

void dfs(const vector<vector<int>>& adj, int u, vector<bool>& vis) {
    vis[u] = true;
    // ... 前序處理 u ...
    for (int v : adj[u])
        if (!vis[v]) dfs(adj, v, vis);
    // ... 後序處理 u ...
}

DFS 的時間戳與邊分類

DFS 過程中為每個頂點記錄「進入時間」\(tin[u]\) 與「離開時間」\(tout[u]\)，可把邊分成四類（有向圖）：

• 樹邊（tree edge）：DFS 樹中實際走的邊。

• 回邊（back edge）：指向祖先 —— 回邊的存在等價於有環。

• 前向邊（forward edge）：指向已完成的子孫。

• 橫向邊（cross edge）：指向其他子樹。

這套「時間戳 + 邊分類」是後續環偵測、拓撲排序、強連通分量、橋與割點的共同基礎。

BFS 與 DFS 的比較

連通性分析

「圖的哪些部分彼此相連？」是最基本的結構問題。本章涵蓋無向圖的連通分量、有向圖的強連通分量，以及二分圖判定。

連通分量 (Connected Components)

在無向圖中，連通分量是一個極大的頂點子集，集合內任兩點都互相可達。找出所有連通分量只需反覆從未拜訪的頂點啟動一次 DFS 或 BFS，並為它們標上同一個編號。

vector<int> components(const vector<vector<int>>& adj) {
    int n = adj.size(), cid = 0;
    vector<int> comp(n, -1);
    for (int s = 0; s < n; ++s) {
        if (comp[s] != -1) continue;
        stack<int> st; st.push(s); comp[s] = cid;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            for (int v : adj[u])
                if (comp[v] == -1) { comp[v] = cid; st.push(v); }
        }
        ++cid;
    }
    return comp;
}

時間 \(O(V+E)\)。連通分量的計數在「朋友圈數量」、「島嶼數量」、「網路是否分裂」等問題中無所不在。

二分圖判定 (Bipartite Check)

判定方法：用 BFS/DFS 做二著色。給起點塗色 0，鄰居塗相反色 1，再相反……若途中發現某條邊兩端同色，則不是二分圖。

bool isBipartite(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);
    for (int s = 0; s < n; ++s) {
        if (color[s] != -1) continue;
        queue<int> q; q.push(s); color[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
                else if (color[v] == color[u]) return false; // 同色衝突
            }
        }
    }
    return true;
}

應用：排班（人 vs. 班次）、配對（求職者 vs. 職缺）、衝突偵測（兩群互斥），都先確認是否為二分圖，再套用第 11 章的二分匹配。

強連通分量 (SCC, Tarjan 演算法)

在有向圖中，「連通」要分得更細。強連通分量（Strongly Connected Component）是極大的頂點子集，集內任兩點 \(u,v\) 都雙向可達（\(u \to v\) 且 \(v \to u\)）。

Tarjan 演算法用一次 DFS 求出所有 SCC。核心是兩個時間戳：

• \(disc[u]\)：\(u\) 的「發現時間」。

• \(low[u]\)：\(u\) 經由 DFS 子樹 + 至多一條回邊，能回到的最早 \(disc\) 值。

搭配一個堆疊存放「目前尚未歸屬」的頂點。當 \(disc[u] = low[u]\) 時，\(u\) 是一個 SCC 的「根」，將堆疊彈出到 \(u\) 為止即構成一個 SCC。

複雜度：\(O(V+E)\)。完整實作見第 14 章 TarjanSCC 類別。

應用：2-SAT 判定、編譯器的相互遞迴函式分組、社群網路的緊密群偵測、死結（deadlock）偵測。

橋與割點 (Bridges & Articulation Points)

在無向圖中，有些邊或點是「網路的咽喉」：

• 割點（articulation point / cut vertex）：移除後會使連通分量增加的頂點。

• 橋（bridge / cut edge）：移除後會使連通分量增加的邊。

它們衡量網路的脆弱性——一座橋斷了，網路就分裂。同樣用 \(disc/low\) 時間戳，一次 DFS 即可求出：

• 邊 \((u,v)\) 是橋 \(\iff low[v] > disc[u]\)（\(v\) 的子樹無法繞過 \(u\) 回到更早的點）。

• 非根頂點 \(u\) 是割點 \(\iff\) 存在子節點 \(v\) 使 \(low[v] \geq disc[u]\)；根頂點是割點 \(\iff\) 它有 \(\geq 2\) 個 DFS 子樹。

應用：電信骨幹網路的單點故障分析、道路網的關鍵橋樑、社群網路的「橋接者」（連接兩個社群的關鍵人物）。完整實作見第 14 章 ArticulationBridge。

拓撲排序 (Topological Sort)

問題定義

給定一個有向無環圖（DAG），拓撲排序是把所有頂點排成一個線性序列，使得對每條邊 \((u,v)\)，\(u\) 都排在 \(v\) 之前。直覺上就是「相依關係的合法執行順序」。

Kahn 演算法（BFS 式）

核心觀念：入度為 0 的頂點沒有任何前置相依，可以最先處理。

1. 計算每個頂點的入度，把入度 0 者全部入列。

2. 反覆取出一個頂點 \(u\) 加入結果，並把它所有出邊「移除」（鄰居入度減 1）；若鄰居入度降為 0 則入列。

3. 若最終排序的頂點數 \(< n\)，代表有環。

vector<int> topoSort(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> indeg(n, 0), order;
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) ++indeg[v];
    queue<int> q;
    for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return (int)order.size() == n ? order : vector<int>{}; // 空 = 有環
}

複雜度：\(O(V+E)\)。

DFS 式拓撲排序

另一種做法：對每個頂點做 DFS，在離開（後序）時把頂點推入堆疊，最後將堆疊反轉即為拓撲序。直覺是：一個頂點所有的後繼都處理完，它才被加入，故它必排在後繼之前。

應用

• 建置系統 / 編譯相依：Makefile、Maven、npm 決定編譯順序。

• 課程先修（LeetCode「課程表」）：判斷能否修完所有課。

• 試算表重算：儲存格公式相依的計算次序。

• 任務排程：專案管理的工序安排（搭配關鍵路徑法）。

環偵測 (Cycle Detection)

「圖中有沒有環？」依有向／無向而有不同做法。環偵測是相依分析、死結偵測、資料一致性檢查的核心。

有向圖：DFS 三色法

為每個頂點維護三種狀態：

• 白色（0，未拜訪）

• 灰色（1，在當前 DFS 路徑上 / 遞迴堆疊中）

• 黑色（2，已完成）

DFS 過程中，若遇到一條指向灰色頂點的邊（即回邊），就代表存在環。

bool dfsCycle(const vector<vector<int>>& adj, int u, vector<int>& color) {
    color[u] = 1;                        // 灰：進入遞迴
    for (int v : adj[u]) {
        if (color[v] == 1) return true;  // 回邊 -> 有環
        if (color[v] == 0 && dfsCycle(adj, v, color)) return true;
    }
    color[u] = 2;                        // 黑：離開
    return false;
}
bool hasCycle(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, 0);
    for (int i = 0; i < n; ++i)
        if (color[i] == 0 && dfsCycle(adj, i, color)) return true;
    return false;
}

無向圖：DFS 父節點法 或 並查集

無向圖中，DFS 時若遇到一個已拜訪且非父節點的鄰居，即代表有環：

bool dfsU(const vector<vector<int>>& adj, int u, int parent, vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) { if (dfsU(adj, v, u, vis)) return true; }
        else if (v != parent) return true;   // 連到非父的已訪點 -> 環
    }
    return false;
}

另一種優雅做法是並查集：逐邊處理 \((u,v)\)，若 \(u,v\) 已在同一集合則成環，否則合併。這正是 Kruskal 避免成環的機制（第 9 章）。

偵測負權環

在加權有向圖中，負權環會讓最短路徑無下界（繞圈無限變小）。Bellman-Ford 在第 \(V\) 次仍能鬆弛任何邊，即代表存在負權環（第 7 章）。

應用對照

最短路徑演算法

最短路徑是圖論最重要、應用最廣的主題：導航軟體、網路路由、遊戲尋路、物流規劃都依賴它。本章依「圖的特性」介紹四種主力演算法，並給出選擇指南。

問題分類

Dijkstra 演算法

核心思想

Dijkstra 解決非負權圖的單源最短路。它是貪婪演算法：維護一個「已確定最短距離」的集合，每次從「尚未確定」的頂點中挑出目前距離最小者，確定它，並用它去鬆弛（relax）鄰居。

以優先佇列實作

用一個最小堆（min-heap）維護候選頂點，每次彈出距離最小者。

vector<long long> dijkstra(const vector<vector<pair<int,int>>>& adj, int s) {
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(adj.size(), INF);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;          // (距離, 頂點) 小根堆
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;          // 過期項目，跳過
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

手算範例

由 0 出發，依序確定：\(dist[0]{=}0 \to dist[2]{=}1 \to dist[1]{=}3\)（經 0→2→1，比直接 0→1 的 4 更短）\(\to dist[3]{=}4 \to dist[4]{=}7\)。最終 \(dist = [0, 3, 1, 4, 7]\)。

重建路徑

只要在鬆弛時記錄前驅 \(parent[v] = u\)，最後從終點沿 \(parent\) 回溯即可得到實際路徑。

0-1 BFS

當邊權只有 0 或 1 時，可用雙端佇列（deque）取代堆，達到 \(O(V+E)\)：權重 0 的邊把鄰居推到隊首（同層），權重 1 的推到隊尾（下一層）。

vector<int> zeroOneBFS(const vector<vector<pair<int,int>>>& adj, int s) {
    vector<int> dist(adj.size(), INT_MAX);
    deque<int> dq;
    dist[s] = 0; dq.push_front(s);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
    }
    return dist;
}

應用：格子地圖中「有些移動免費、有些要花費 1」的最短代價問題。

Bellman-Ford 演算法

核心思想

Bellman-Ford 能處理負權邊，並能偵測負權環。它不貪婪，而是「暴力鬆弛」：對所有邊重複鬆弛 \(V-1\) 次。

struct Result { vector<long long> dist; bool negCycle; };
Result bellmanFord(int n, const vector<array<int,3>>& edges, int s) {
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(n, INF); dist[s] = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool relaxed = false;
        for (auto& e : edges) {            // e = {u, v, w}
            if (dist[e[0]] == INF) continue;
            if (dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
                relaxed = true;
            }
        }
        if (!relaxed) break;               // 提早收斂
    }
    bool neg = false;
    for (auto& e : edges)
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) neg = true;
    return {dist, neg};
}

複雜度：\(O(VE)\)。雖比 Dijkstra 慢，但能處理負權。SPFA 是其佇列優化版，平均較快但最差仍 \(O(VE)\)。

Floyd-Warshall 演算法

求所有頂點對之間的最短路。核心是極簡的動態規劃：考慮「只允許經過前 \(k\) 個頂點作中繼」的最短路，逐步放寬 \(k\)。

\[d_{ij}^{(k)} = \min\!\left(d_{ij}^{(k-1)},\; d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right).\]

// d[i][j] 初始化為邊權，無邊為 INF，d[i][i]=0
for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];

複雜度：時間 \(O(V^3)\)、空間 \(O(V^2)\)。適合頂點數較小（\(V \lesssim 400\)）但需要全源資訊的情境，也能用來求傳遞閉包（哪些點互相可達）。

A* 搜尋

A* 是 Dijkstra 的「有方向性」版本，常用於遊戲與地圖尋路。它用一個啟發函數 \(h(v)\) 估計 \(v\) 到終點的距離，以 \(f(v) = g(v) + h(v)\) 排序（\(g\) 為已知起點距離）。

• 若 \(h\) 為可採納（admissible，從不高估），A* 保證找到最短路。

• 常見啟發：格子地圖用曼哈頓距離或歐氏距離。

• \(h \equiv 0\) 時，A* 退化為 Dijkstra。

A* 透過優先探索「看起來更接近終點」的方向，大幅減少展開的節點數，但答案品質取決於啟發函數的設計。

最短路演算法選擇指南

最小生成樹 (Minimum Spanning Tree)

問題定義

直覺：用最少的「成本」把所有點連起來。例如鋪設電纜連通所有城市、讓總線長最短。

Kruskal 演算法

策略：把所有邊依權重由小到大排序，依序嘗試加入；若一條邊的兩端點尚未連通（用並查集判斷）就加入，否則會成環，跳過。加滿 \(n-1\) 條邊即完成。

struct Edge { int u, v, w; };
long long kruskal(int n, vector<Edge> edges) {
    sort(edges.begin(), edges.end(),
         [](const Edge& a, const Edge& b){ return a.w < b.w; });
    DSU dsu(n);
    long long total = 0; int used = 0;
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {         // 不成環才加入
            total += e.w;
            if (++used == n - 1) break;
        }
    }
    return total;
}

複雜度：排序主導，\(O(E \log E)\)。Kruskal 用邊串列最自然，特別適合稀疏圖。

Prim 演算法

策略：類似 Dijkstra，從任一頂點開始「長樹」。維護一個優先佇列，每次挑出「連接樹與樹外、權重最小」的邊，把對應的新頂點納入樹中。

long long primMST(const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<bool> inTree(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    long long total = 0; int taken = 0;
    pq.push({0, 0});                       // (權重, 頂點)
    while (!pq.empty() && taken < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inTree[u]) continue;
        inTree[u] = true; total += w; ++taken;
        for (auto [v, wt] : adj[u])
            if (!inTree[v]) pq.push({wt, v});
    }
    return total;
}

複雜度：\(O((V+E)\log V)\)。Prim 用鄰接串列，較適合稠密圖（搭配鄰接矩陣的 \(O(V^2)\) 版本在稠密時甚至更快）。

Kruskal vs. Prim

應用

• 網路 / 電纜 / 管線佈建：以最低總成本連通所有節點。

• 群聚分析：刪除 MST 中最長的 \(k-1\) 條邊，可得到 \(k\) 個群（單連結聚類）。

• 近似演算法：MST 是旅行推銷員問題（TSP）2-近似解的基礎。

• 影像分割：以像素相似度為權重，用 MST 切割影像區域。

並查集 (Disjoint Set Union)

問題與動機

並查集（Disjoint Set Union, DSU / Union-Find）維護一組「不相交集合」，支援兩個操作：

• find(x)：回傳 \(x\) 所屬集合的代表元（root）。

• unite(x, y)：合併 \(x\) 與 \(y\) 所在的兩個集合。

它是 Kruskal、連通性維護、環偵測的幕後功臣，也是動態連通問題的標準解。

兩大優化：路徑壓縮 + 按秩合併

樸素實作的樹可能退化成鏈，使 find 變 \(O(n)\)。兩個優化讓它幾乎變成常數：

• 路徑壓縮（path compression）：find 時把沿途節點直接掛到根下。

• 按秩 / 按大小合併（union by rank/size）：把較矮的樹掛到較高的樹下，避免長高。

class DSU {
    vector<int> parent, rank_;
public:
    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);  // 各自成集
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];       // 路徑壓縮（折半）
            x = parent[x];
        }
        return x;
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;              // 已在同集（成環）
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};

應用

• Kruskal MST：判斷加邊是否成環。

• 動態連通性：逐步加邊，隨時查詢兩點是否連通。

• 連通分量計數：合併同時維護分量數。

• 離線查詢：如「島嶼數量 II」逐格加陸地。

• 帶權並查集：可維護到根的相對關係（如「食物鏈」種類推理）。

網路流 (Network Flow)

網路流是圖論中極具威力的建模工具：許多看似無關的問題（匹配、分配、切割、排程）都能化約成「最大流」來求解。

最大流問題

Ford-Fulkerson 與 Edmonds-Karp

核心觀念：反覆在殘餘網路（residual graph）中尋找一條從 \(s\) 到 \(t\) 的增廣路徑（augmenting path），沿途增加流量，直到找不到為止。

• 殘餘容量：邊 \((u,v)\) 還能再送的量 \(= c(u,v) - f(u,v)\)。每條正向邊都伴隨一條反向邊，容量初始為 0，用來「反悔」先前的流。

• Ford-Fulkerson：用 DFS 找增廣路，整數容量下會終止，但複雜度依賴流值。

• Edmonds-Karp：固定用 BFS 找最短增廣路，複雜度 \(O(VE^2)\)，與容量大小無關。

struct MaxFlow {
    struct E { int to, rev, cap; };
    vector<vector<E>> g;
    MaxFlow(int n) : g(n) {}
    void addEdge(int u, int v, int cap) {
        g[u].push_back({v, (int)g[v].size(), cap});
        g[v].push_back({u, (int)g[u].size()-1, 0}); // 反向邊
    }
    int run(int s, int t) { /* BFS 找增廣路並更新殘餘圖，見第 14 章 */ }
};

最大流最小割定理

這個對偶關係極為深刻：求「最多能送多少」等價於求「最便宜的切斷方式」。它把流問題與割問題（影像分割、可靠度分析）連結起來。

建模的藝術：問題化約

網路流真正的威力在於把其他問題翻譯成流：

• 二分匹配：源點連左部、右部連匯點，所有容量設 1，最大流即最大匹配（見下章）。

• 帶下界 / 多源多匯：加超級源匯轉換。

• 最小成本最大流：邊再附成本，用 SPFA/Bellman-Ford 找最便宜增廣路——用於指派、運輸問題。

• 專案選擇 / 最大權閉合子圖：化為最小割。

二分匹配 (Bipartite Matching)

問題定義

給定二分圖（左部 \(L\)、右部 \(R\)），匹配是一組沒有共用端點的邊。最大匹配即邊數最多的匹配。典型情境：把求職者配到職缺、學生配到專題、計程車配到乘客。

匈牙利演算法（增廣路）

核心是增廣路徑：一條交替走「未匹配邊、已匹配邊」、且兩端都是未匹配點的路徑。沿此路徑翻轉所有邊的匹配狀態，匹配數就 \(+1\)。對每個左部點嘗試找增廣路即可。

bool tryMatch(int u, vector<vector<int>>& adj,
              vector<int>& matchR, vector<bool>& used) {
    for (int v : adj[u]) {
        if (used[v]) continue;
        used[v] = true;
        if (matchR[v] == -1 || tryMatch(matchR[v], adj, matchR, used)) {
            matchR[v] = u;                 // 配對 / 重新配對
            return true;
        }
    }
    return false;
}

複雜度：\(O(V \cdot E)\)。資料量大時可用 Hopcroft-Karp 達 \(O(E\sqrt{V})\)。

應用

• 指派問題：員工↔︎任務、課程↔︎教室、機器↔︎工件。

• 排班：醫師↔︎值班時段。

• 推薦 / 廣告：在限制下把廣告位配給廣告主（常用最小成本流的加權版）。

進階主題

本章彙整幾個常在競賽與實務出現的進階結構，著重觀念與應用，完整實作見第 14 章。

最近共同祖先 (LCA)

在有根樹中，兩節點 \(u,v\) 的最近共同祖先是同時為兩者祖先、且深度最大的節點。它能高效回答「樹上兩點距離」、「路徑查詢」等問題。

倍增法（Binary Lifting）：預處理 \(up[k][v] =\)「\(v\) 的第 \(2^k\) 個祖先」。查詢時先把較深的點上提到同深度，再一起往上跳。

• 預處理 \(O(V \log V)\)，每次查詢 \(O(\log V)\)。

• 樹上兩點距離 \(= depth[u] + depth[v] - 2\,depth[\text{lca}(u,v)]\)。

應用：階層分類、family tree、網路拓撲的共同上游、版本控制的共同祖先 commit。

歐拉路徑與歐拉迴路

歐拉路徑是「不重複地走過每一條邊恰好一次」的路徑；若起終點相同則為歐拉迴路。這正是著名的「七橋問題」。

• 無向連通圖存在歐拉迴路 \(\iff\) 所有頂點度數皆偶數。

• 存在歐拉路徑（非迴路）\(\iff\) 恰有兩個奇數度頂點。

• Hierholzer 演算法可在 \(O(E)\) 內構造。

應用：DNA 片段重組、郵差路線、一筆畫問題。

最小生成樹的延伸

• 次小生成樹：在 MST 基礎上換一條邊。

• 有向最小生成樹（樹形圖）：朱劉演算法（Chu-Liu/Edmonds）。

• Steiner 樹：只需連通指定子集（NP-hard，常用近似）。

圖著色與最大團

圖著色：給頂點塗色使相鄰異色，最少用幾種色（色數）是 NP-hard。應用於排程、暫存器配置、頻率分配。最大團（互相皆相鄰的最大頂點集）同為 NP-hard，但在實務上常用啟發式或位元優化暴搜。

現代延伸：圖神經網路 (GNN)

近年圖機器學習快速崛起。圖神經網路（GNN）透過訊息傳遞（message passing）學習節點 / 邊 / 整圖的向量表示：每個節點反覆「聚合鄰居資訊 → 更新自身狀態」，多輪後即捕捉到局部結構。

• 代表架構：GCN（圖卷積）、GraphSAGE（取樣聚合）、GAT（注意力）。

• 任務型態：節點分類、連結預測、整圖分類。

• 應用：分子性質預測、推薦系統、詐欺偵測、交通預測、知識圖譜補全。

解題策略：如何辨識題型

面對一道新題，最關鍵的是把問題翻譯成圖並辨識題型。本章提供一套系統化的思考流程。

第一步：辨識圖的結構

問自己四個問題：

1. 頂點與邊是什麼？ 物件是頂點，關係是邊。格子？狀態？單字？

2. 有向還是無向？

3. 有權還是無權？權重可為負嗎？

4. 圖是明確給定，還是隱式狀態空間？

第二步：題型 → 演算法對照表

第三步：常見陷阱檢查表

真實世界的應用

圖演算法不是學術玩具——它們是現代科技基礎建設的核心。本章蒐集 2026 年產業實例。

導航與地圖

Google Maps、Waze 的路線規劃本質是加權最短路。實務上不直接跑 Dijkstra（太慢），而是用雙向搜尋、A* + 地標啟發、以及收縮層級（Contraction Hierarchies）等預處理技術，把全國路網的查詢壓到毫秒級。即時路況則把邊權動態更新。

社群網路

• 好友推薦：「你可能認識的人」用 BFS 找二度人脈、共同好友數。

• 影響力 / 排名：PageRank（特徵向量中心性的變體）衡量節點重要性。

• 社群偵測：用連通分量、Louvain、標籤傳播找出緊密群體。

• Netflix 以自研「Graph Abstraction」服務社交圖與服務拓撲，尖峰處理近每秒千萬次操作、橫跨 650 TB 圖資料。

詐欺偵測與金融

詐欺本質是連結問題——詐騙集團以「環狀金流、共用裝置、共用身分」運作，傳統逐筆分析難以察覺。圖資料庫（如 Neo4j）用以下技巧揭露詐欺網：

• 連通分量 / 社群偵測找出詐欺環。

• PageRank / 中心性找出異常具影響力的帳戶（人頭中樞）。

• 節點相似度（Jaccard）偵測「共用 SSN / Email / 電話」的模仿帳戶。

• 多跳遍歷追蹤洗錢的資金流向。

Neo4j 宣稱以圖比關聯式資料庫快上千倍揭露此類模式。

推薦系統

電商與串流以二分圖（使用者↔︎商品）建模。協同過濾透過圖遍歷找「和你相似的人也喜歡的東西」。一個典型 Cypher 查詢的精神：找「我喜歡的電影 → 也喜歡它的其他人 → 他們喜歡但我還沒看的電影」，依出現次數排序推薦。

基礎設施與供應鏈

• 網路路由：OSPF 用 Dijkstra 計算最短路徑樹；BGP 處理跨自治系統路由。

• 供應鏈：以圖建模多階供應商相依，分析斷點風險（割點 / 橋）與替代路徑。Google BigQuery Graph 讓企業在 PB 級資料上做多跳相依分析。

• 電網 / 電信：割點分析找單點故障；最大流評估容量。

編譯器、建置與排程

• 相依解析：套件管理（npm、Maven）、建置系統用拓撲排序決定順序、用環偵測抓循環相依。

• 暫存器配置：以圖著色決定變數該放哪個暫存器。

• 指令排程 / 關鍵路徑：DAG 上的最長路徑決定專案最短工期。

生物資訊與其他

DNA 定序的片段重組用歐拉路徑（de Bruijn 圖）；蛋白質交互作用網路、代謝路徑分析、藥物分子的性質預測（GNN）都以圖為核心。此外，知識圖譜（Knowledge Graph）支撐了搜尋引擎與大型語言模型的 GraphRAG 檢索。

完整 C++ 實作

本章提供一份完整、可直接編譯執行的 C++17 程式碼，涵蓋全書 17 個核心演算法。此程式碼已實際編譯（g++ -std=c++17 -O2）並執行驗證通過。

編譯與執行

g++ -std=c++17 -O2 -Wall -Wextra -o graph_algorithms graph_algorithms.cpp
./graph_algorithms

原始碼

執行輸出（節錄）

1. BFS shortest distance (unweighted)
  dist from 0 = 0 1 1 2 3 4
3. Topological sort (Kahn)
  order: 0 1 2 3 5 4
5. SCC (Tarjan): components count = 2
  comp[v] = 1 1 1 0 0 0
6. Articulation points & bridges
  articulation = 2 3 4
  bridges = (3,4) (2,3)
8. Dijkstra: dist from 0 = 0 3 1 4 7
10. Bellman-Ford: dist from 0 = 0 2 7 4 -2  (no negative cycle)
12. Kruskal MST: total weight = 14
13. Prim MST:    total weight = 14
15. Edmonds-Karp max flow s->t = 23
16. Bipartite matching = 4
17. LCA(6,4) = 1 dist = 3 ; LCA(6,5) = 0 dist = 5

練習題

以下練習依難度分級。建議先獨立思考「該用哪個演算法、如何建圖」，再動手實作。多數題目可在 LeetCode、Codeforces 找到對應題。

入門（走訪與連通）

1. 島嶼數量：給 0/1 格子地圖，求相連陸地塊數。（DFS/BFS 或 並查集）

2. 無權最短路：求迷宮起點到終點最少步數。（BFS）

3. 二分圖判定：判斷是否可二著色。（BFS 二著色）

4. 朋友圈：給朋友關係矩陣求圈數。（並查集）

5. 克隆圖：深拷貝一張無向圖。（DFS + 雜湊表）

進階（排序與最短路）

1. 課程表 II：輸出可行修課順序，或判斷不可能。（拓撲排序）

2. 網路延遲時間：信號傳到所有節點的最短時間。（Dijkstra）

3. K 站中轉最便宜航班：帶限制的最短路。（修改版 Dijkstra / Bellman-Ford）

4. 路徑最小體力消耗：邊權為高度差，最小化路徑最大邊。（Dijkstra 變體 / 二分 + BFS）

5. 連接所有點的最小費用：曼哈頓距離為權的 MST。（Prim / Kruskal）

挑戰（流、匹配、進階）

1. 最大二分匹配：求職者與職缺配對。（匈牙利 / 最大流）

2. 逃生問題：多源到邊界的最大不相交路徑。（最大流 / 最小割）

3. 關鍵連接（橋）：找出網路中所有橋。（Tarjan）

4. 樹上路徑查詢：多次詢問兩點距離。（LCA 倍增）

5. 重新規劃路線：使所有點能到達 0 的最少改向邊數。（DFS / BFS 建雙向圖）

6. 套利偵測：給匯率表判斷是否存在套利。（Bellman-Ford 找負權環）

總結與延伸閱讀

複雜度速查表

學習路徑建議

1. 打地基：徹底搞懂鄰接串列、BFS、DFS。八成的圖題都建立在這三者之上。

2. 連通性家族：連通分量、二分圖、拓撲排序、環偵測——它們都是 DFS/BFS 的變體。

3. 最短路家族：先 Dijkstra，再 Bellman-Ford 與 Floyd-Warshall，理解何時用哪個。

4. 生成樹與並查集：Kruskal/Prim/DSU 一起學，互相呼應。

5. 進階：網路流、匹配、LCA、Tarjan，依需求深入。

6. 現代延伸：圖資料庫（Neo4j、Cypher）、圖機器學習（GNN）。

延伸閱讀

• Introduction to Algorithms（CLRS），第 22–26 章——圖演算法的權威教科書。

• Competitive Programming（Halim 兄弟）——競賽導向、實作豐富。

• Algorithm Design（Kleinberg & Tardos）——強調建模與證明。

• Graph Algorithms（O’Reilly, Needham & Hodler）——以 Neo4j / Spark 講實務圖分析。

• cp-algorithms.com——線上免費、涵蓋完整的競賽演算法參考。

• PyTorch Geometric 官方教學——入門圖神經網路（GNN）的最佳起點。