【講義】基礎圖論

零、前言

考慮以下問題：

有

$n$ 座城市，以及

$m$ 條道路。每條道路連接兩個城市

$(u,v)$。請問從城市

$1$ 走到城市

$n$，最少必須經過幾個城市？

這道題目是一道標準的圖論問題，本章節將探討如何解決類似的題目。

一、圖的介紹及基本概念

一個圖（Graph）包含一些節點（Vetex）和一些邊（Edge）。我們可以一個由節點集合

$V$ 和邊集合

$E$ 構成的圖

$G$，表示為

$G=(V,E)$。圖用來描述一些節點之間的連接關係。例如節點可能可以代表一些城市、車站。而每一條邊表示了兩個節點的連接關係，就像道路和鐵軌。

一張由 4 個節點和 4 條邊構成的圖

以下是圖論領域使用的名詞和基本概念的介紹：

1. 有向圖、無向圖：
   無向圖中的邊為「無向邊」。無向邊

   $(u,v)$ 代表從
   $u$ 可以到達
   $v$，反之也可到達。
   $(u,v)$ 也可記為
   $u\to v$。
   有向圖中的邊為「有向邊」。有向邊
   $(u,v)$ 代表從
   $u$ 可以到達
   $v$。

   有向圖

2. 相鄰（adjacent）：當節點

   $u,v$ 間存在一條邊，則稱
   $u,v$ 相鄰

3. 度數：點

   $u$ 的度數為相鄰節點的數量
   1. 入度：點
      $u$ 的入度為指向
      $u$ 的邊的數量
   2. 出度：點
      $v$ 的出度為指向
      $v$ 的邊的數量

4. 邊權：一條邊可以有數值

   $w$，稱
   $w$ 為該邊的「邊權」。邊權可能代表兩點間的距離、花費、最大流量等，其意義視用途而定。

   有邊權的無向圖

5. 點權：一個節點可以有數值

   $w$，稱
   $w$ 為該點的「點權」。點權可能代表該點的花費等，其意義視用途而定。

6. 重邊：當點

   $u,v$ 間有不只一條邊，稱
   $u,v$ 間有「重邊」。

7. 路徑：有起點

   $s$ 和終點
   $t$，從
   $s$ 走到
   $t$ 途中經過的邊的序列。以下圖為例，
   $(1\to 2,2\to 3,3\to 4)$ 為
   $1$ 到
   $3$ 的路徑之一。

8. 環：一個路徑的起點和終點相同，則該路徑稱為「環」。

9. 迴路：一個路徑經過了所有的點洽一次，且起點和終點相同，則該路徑稱為「迴路」。

10. 自環：一條邊的兩端為相同節點，稱為「自環」

11. 連通：若點

    $s$ 存在一條路徑到點
    $t$，則稱
    $s$ 和
    $t$ 「連通」。

$\{1,2,3\},\{4,5,6\}$ 各為一個連塊

1. 連通塊：如果點集
   $S$ 中的所有節點都互相連通，稱
   $S$ 為「連通塊」。
2. 簡單圖：若圖
   $G$ 不存在自環和重邊，則稱
   $G$ 為「簡單圖」。
3. 子圖：若圖
   $G$ 的邊和節點，皆為圖
   $G$ 的子集，則稱
   $C$ 為
   $G$ 的「子圖」。
4. 反圖：將有向圖
   $G$ 的每一條邊反過來（原本是
   $u\to v$ 改成
   $v\to u$），則新的圖和
   $G$ 互為反圖。
5. 完全圖：若無向簡單圖
   $G$ 滿足任意兩節點皆存在一條邊，稱
   $G$ 為完全圖。
6. 補圖：圖
   $G$ 的補圖
   $cG$，和
   $G$ 有一樣的節點，而圖
   $cG$ 中
   $(u,v)$ 有邊若且唯若
   $(u,v)$ 在
   $G$ 中沒有邊。把
   $G$ 和
   $cG$ 加在一起，可以得到一張完全圖。
7. 二分圖：一張圖可以將節點拆成互斥的集合
   $U,V$，使得集合中沒有相鄰的節點，則該圖為二分圖。

二、圖的儲存

常見圖的儲存有三種方式：直接存邊、鄰接矩陣和鄰接串列。

無向圖中的邊

$(u,v)$ 代表

$u$ 和

$v$ 可以互相抵達，因此儲存時我們會將邊無向邊

$(u,v)$ 拆解成兩條有向邊

$u\to v$ 和

$v\to u$。

鄰接矩陣

用一個

$|V|\times |V|$ 的陣列

$G$ 表示圖。若存在邊

$u\to v$，記

$G[u][v]=1$，否則

$G[u][v]=0$。若

$u\to v$ 有邊權

$w$，可記

$G[u][v]=w$。

const int N = 1e3; // 該題測資中，最多 N 個節點

int n; // |V| = n
int G[N][N]; // 若 G[i][j] = 1, 代表 i -> j

加入一條邊 u -> v ：

G[u][v] = 1;

遍歷 u 的相鄰節點，複雜度：

for (int v = 1; v<=n; v++){
	if (G[u][v] == 1){
		// do something...
	}
}

實際存法可以依照需求調整，例如若有

$u\to v$ 且邊權為

$w$，記

$G[u][v]=w$；否則

$G[u][v]=INF$。

鄰接串列

用一個陣列

$G$ 表示圖，

$G[u]$ 為所有和

$u$ 相鄰的點。通常

$G[u]$ 為一個可變長度陣列，實作上使用 vector。

const int N = 1e5; // 該題測資中，最多 N 個節點

int n; // |V| = n
vector<int> G[N]; // G[i] 為一 vector，vetor 當中儲存所有和 i 相鄰的節點

加入一條邊 u -> v ：

G[u].push_back(v);

遍歷 u 的相鄰節點：

for (auto v: G[u]){
	// do something...
}

直接存邊

直接將每一條邊的儲存在陣列裡。

struct Edge {
	int u, v; // u -> v
};

vector<Edge> e;

加入一條邊 u -> v ：

e.push_back( {u, v} );

我們通常不使用此方法來尋找 u 的相鄰節點。

方法優劣分析

最常見的需求是將一張圖的每個點、每條邊遍歷過一次。若使用鄰接矩陣，對於每個點都需要

$O|V|$ 的時間，總複雜度為

$O|V{|}^2$。若使用鄰接矩陣，儘管對於一個點，遍歷所有鄰居的最糟時間為

$O(|V|)$，但經觀察可發現，每條邊至多被存取 1 到 2 次，因此總複雜度為

$O(|V|+|E|)$。大部分情況下，我們使用鄰接串列來儲存一張圖。

三、圖的遍歷

遍歷一張圖有很多種方法：從節點

$1$ 到

$n$、先奇數再偶數等等…。然而以上的遍歷方法對我們幫助不大。在絕大部分情況下，我們使用兩種方法來遍歷一張圖：深度優先搜尋（Depth-First Search, DFS）和廣度優先搜尋（Breadth-First Seach, BFS）。

考慮下面一張圖。我們將從

$1$ 開始，經過每一條邊，走訪所有的點：

我們先從

$1$ 走到

$2$，接著會面臨許多岔路。DFS 的精神是深度優先，因此會優先把一條分支走死，再回到岔路口走把下一條分支走死。例如：造訪

$1,2$ ，遇到岔路，先往下造訪

$3,4$，接著回到

$2$，往下造訪

$6,7$，接著回到

$2$，往下造訪

$8$。

BFS 的精神則是廣度優先，當遇到岔路時，會同時走訪所有分支，每條分支從近到遠。例如：造訪

$1,2$，遇到岔路，造訪

$2,6,8$；接著造訪

$4,7$。

下面將深入介紹 DFS 和 BFS 的特性和實作。

深度優先搜尋（Depths-First Search）

DFS 的核心精神：盡可能的探索一條分支，可以簡單地用遞迴來實作：

vector<int> G[N];
int vis[N];

void dfs (int u) {
    vis[u] = 1;
    
    for (auto v: G[u]) {
        if (vis[v]) continue;
        dfs(v);
    }
}

上述的函數在遇到岔路時，會往其中一個 DFS 下去，而下一層的遞迴亦復如是。當其中一條岔路 v 探索完畢， dfs(v) 會 return 回來，接著便進行下一次的迴圈，造訪下一條岔路。

廣度優先搜尋（Breadth-First Search）

BFS 會從離起點近的開始造訪。更正式的說，我們將造訪分為第

$0,1,2,\dots$ 回合。而第

$0$ 回合，造訪起點；下個回合，造訪所有距離為

$1$ 的節點；再下個回合，造訪所有距離為

$2$ 的節點……。如此，就能從近到遠造訪過所有節點，且所有分支同時進行。

BFS 的演算法概念如下：

將起點加入回合 0
將起點標記為已造訪
遍歷現在的回合 k = 0, 1, 2, ... :
	遍歷所有屬於回合 k 的節點 u :
		遍歷所有相鄰於 u 且未造訪過的節點 v :
			將 v 標記為已造訪
			將 v 加入回合 k+1

BFS 圖示

上述演算法，可以確保我們在第

$k$ 回合造訪起點

$u$，若且唯若

$u$ 距離起點為

$k$。正確性可用歸納法證明，在此略過。

事實上，我們可以不用為每個回合需要遍歷的節點開一個陣列來維護。善用「佇列（queue）」的特性，我們可以達成一樣的效果。假設有一佇列

$Q$ 儲存了第

$k$ 回合的所有節點：我們依序從

$Q$ 拿出節點

$u$，並將相鄰於

$u$、屬於回合

$k+1$ 的節點加入

$Q$，直到

$Q$ 中沒有第

$k$ 回合的節點為止。

此時會發現，佇列

$Q$ 中包含且僅包含所有屬於回合

$k+1$ 的節點。這是因為所有屬於回合

$k+1$ 的節點，都是「只會且一定會」被屬於回合

$k$ 的節點發現。加上佇列「先進後出」的特性，我們便能依序遍歷每個回合。而當某個回合的點都被拿出

$Q$，卻沒有發現下個回合的節點時，演算法結束。

以下為 BFS 的實作範例：

vector<int> G[N];
int vis[N], round[N];
queue<int> q;

void bfs(int src) {
    q.push(src)
    vis[src] = 1;
		round[src] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto v: G[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
						round[v] = round[u] + 1;
            q.push(v);
        }
    }
}

習題

• TIOJ 1209
• TIOJ 1081
• TIOJ 2062
• TIOJ 1099
• CF 370A
• CF 1549B

四、樹

「無根樹」為無向圖的一個特例。當一個連通無向圖沒有環，便稱「樹」。無根樹還有以下的性質，並且這些性質同時可以為樹的定義：

• 有
  $n$ 個節點，
  $n-1$ 條邊的連通圖
• 任兩節點間有恰一條簡單路徑
• 沒有環，並且在加入邊
  $(u,v),u\ne v$ 後一定會形成一個環

我們可以為樹定義一個根，稱為「有根樹」，當規定了根節點，節點間就會產生上下階層的關係。下圖是根節點為

$1$ 的有根樹，我們以節點

$3$ 為例說明有根樹的概念和名詞：

• $2$ 為
  $3$ 的「父節點」
• $4,5$ 為
  $3$ 的「子節點」
• $4,5,6,7,8$ 皆為
  $3$ 的「後代」，而
  $3$ 和其後代構成
  $3$ 的「子樹」
• 「葉節點」為沒有後代的節點，如
  $4,6,7,8,9$
• 「深度」為根節點到自己的距離，例如
  $3$ 的深度為
  $2$
• 「高度」為後代中到自己的最大距離，例如
  $3$ 的高度為
  $2$

走訪一顆樹時，我們從根節點開始。若該樹沒有根，則使任一節點為根。樹是圖一個特例，走訪、儲存樹的程式碼和圖一樣，但我們可以稍做優化：在圖中，我們使用

$vis[]$ 陣列確保每個節點只會被造訪到一次，在樹當中則只要不往父節點走，就可以避免造訪到重複節點，因為剩下的節點一定是子節點、沒有被造訪過。

void dfs (int u, int fa) {
	for (auto v: G[u]) {
		if (v == fa) continue;
		dfs(v, u);
	}
}

樹深度

定義樹深度

$d[i]$：根節點到

$i$ 的最短距離。給定一顆有根樹，求每個節點的樹高度。

我們考慮使用動態規劃來解決此問題。由於在樹上做 DP，我們稱這個技巧為樹 DP：

• 狀態：
  $dp[i]$ 代表節點
  $i$ 的深度
• 轉移：
  $dp[u]=dp[fa]+1$
• 基底：
  $dp[1]=0$

由於基底在根節點處，我們需要從自己把答案推廣至子節點。範例程式碼如下：

int n;
vector<int> G[N];

int dep[N];

void dfs(int u, int fa){
    for (auto v: G[u]){
				if (v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

樹高度

定義樹高度

$h[i]$  ：離

$i$ 最遠的子孫節點的距離。給定一顆有根樹，求每個節點的樹高度。

我們一樣可以使用樹 DP 來解決此問題：

• 狀態：
  $dp[i]$ 代表
  $i$ 節點的高度
• 轉移：
  $dp[u]=max\{dp[v_0],dp[v_1],\dots \}+1$，
  $v$ 為
  $u$ 的子節點
• 基底：
  $dp[leaf]=0$，
  $leaf$ 為所有葉節點

由於基底在葉節點處，我們必須要從子節點的答案求出自己的答案：

int dp[N];
vector<int> G[N];

void dfs(int u, int fa) {
  for (auto v: G[u]) {
    if (v == fa) continue;
    dfs(v, u);
    dp[u] = max(dp[v]+1, dp[u]);
  }
}

樹直徑

給定一顆無根樹，求最遠點對的距離。

我們設任一點為根。有一點

$u$，若要最大化以

$u$ 作為最淺的節點的一條路徑的長度，一定是來自不同子節點的子樹中最遠和次遠的節點形成的點對。以下圖為例：樹直徑為以

$7,10$ 為兩端的路徑。而

$2$ 作為該路徑上深度最淺的節點，其來自不同子節點的最遠的點分別為

$7$ 跟

$10$。

因此，我們對於每個節點求

$h1[u]$ 代表

$u$ 的高度，

$h2[u]$ 代表來自高度次高的子節點的高度

$+1$。只要遍歷過所有

$u$，找到最大的

$h1[u]+h2[u]$ 便是答案。

void h1[N], h2[N];

void update(int u, int h){
    if (h >= h1[u]){
        h2[u] = h1[u];
        h1[u] = h;
    }
    else if (h > h2[u]){
        h2[u] = h;
    }
}

void dfs(int u, int p){
    for (auto v: G[u]){
        if (v == p) continue;
        dfs(v, u);
        update(u, h1[v]+1);
    }
}

習題

• CSES 1674
• Luogu 1352
• TCIRCOJ. d115
• TCIRCOJ. d025

五、有向無環圖

有向無環圖（Directed acyclic graph），故名思義，為無環的有向圖。有向無環圖和樹一樣，都是重要的特例。圖上許多的問題在 DAG 和樹上，都會有更好、更優雅或更簡單的演算法。

DAG 一重要特性，就是在 DAG 上可以 DP。考慮

$u\to v$，

$v$ 為

$u$ 的轉移來源，若圖中有環則會造成循環依賴；反之在 DAG 上，可以順利完成 DP，而出度為 0 的節點便是 DP 中的「基底」（不必遞迴求的狀態）。

而若將 DP 的不同狀態，都當成一個節點，轉移視為有向邊，那也會形成一張 DAG。

拓樸排序

拓樸排序的定義：有一張有向圖

$G$，求一個節點到排序，使得若有有向邊

$u\to v$，則

$u$ 在

$v$ 之前。考慮以下問題：

有

$n$ 堂課，每堂課都可能必須先修某些課後才能修。請找出任一種合法的修課順序，使得每堂課修到恰一次。

我們可以把每堂課當做一個節點，而當修

$v$ 前，必須先修

$u$，則我們建一條邊

$u\to v$。求一種合法的修課順序，便是拓樸排序。

拓樸排序示例

例如在上圖中，

$1,6,2,3,4,5$ 和

$1,2,4,6,3,5$ 都是一種合法的修課順序，也就是拓樸排序。而顯然若圖中存在環，我們便沒有辦法求出拓樸排序；反之，若該圖是 DAG，則一定能求出一種拓樸排序。

以下講解拓墣排序的第一種求法。我們可以很自然地想到，對於那些沒有入度的節點，我們可以把他們拔除，並加入排序裡。若產生了新的沒有入度的節點，我們可以再把他們拔除，如此持續下去，直到所有點被拔除。

以上圖為例：我們可以先拔除

$1$；此時

$2$ 和

$6$ 已經沒有入度，我們可以自由選擇拔除何者，這裡拔除

$2$；然後依序拔除

$6$、

$4$、

$3$ 、

$5$。我們就可以得到拓樸排序

$1,2,6,4,3,5$。

若在演算法的過程，找不到可以拔除（入度為零）的節點，但還有節點沒有被拔除，則該圖不存在拓樸排序，也就是該圖有環。

具體上，我們先求出

$ind[u]$ 代表

$u$ 的入度，再把所有

$ind[u]=0$ 的

$u$ 加入待移除的行列。而在拔除一個節點時，則必須拔除該節點連出去的所有邊

$u\to v$，我們做

$ind[v]--$。若此時

$ind[v]=0$，則將

$v$ 也加入帶移除的行列。

vector<int> G[N];
vector<int> result;
vector<int> to_remove;

int ind[N];
int n;

bool topo_sort() {  // do topological sort, return if G is a DAG
  for (int i=1; i<=n; i++)
    for (auto v: G[i])
      ind[v]++;
  for (int i=1; i<=n; i++)
    if (ind[i] == 0)
      to_remove.push_back(i);
    
  while (to_remove.size()){
    int u = to_remove.back();
    result.push_back(u);
    to_remove.pop_back();
    
    for (auto v: G[u]) {
      ind[v]--;
      if (ind[v] == 0) {
        to_remove.push_back(v);
      }
    }
  }

  return n == result.size();
}

拓樸排序也可以用 DFS 來求。我們可以將拓樸排序的逆序，當成 DP 的計算順序。因此求拓樸排序時，可以直接在圖上 Top-Down DP。

vector<int> G[N];
vector<int> result;

int state[N];
int n;
int has_cycle;

void dfs (int u) {
  if (state[u] < 0)
    has_cycle = 1;

  if (state[u] == 0) {
    state[u] = -1;
    for (auto v: G[u]) {
      dfs(v);
    }
    state[u] = 1;
    result.push_back(u);
  }
}

int topo_sort() {    // do topological sort, return if G is a DAG
  for (int i=1; i<=n; i++)
    dfs(i);
  reverse(result.begin(), result.end());
  return !has_cycle;
}

用 DFS 來求拓樸排序的好處是，當需要再 DAG 上 DP 時，不需要先求一次拓樸排序再做 Bottom-UP，直接以上述的程式碼修改即可。

習題

• CSES 1681
• CF 510C
• ZJ a454