【講義】基礎圖論
===
## 零、前言
考慮以下問題：
> 有 $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 \rightarrow 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 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 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 \rightarrow v$ 改成 $v \rightarrow 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 \rightarrow v$ 和 $v \rightarrow u$。
### 鄰接矩陣
用一個 $|V| \times |V|$ 的陣列 $G$ 表示圖。若存在邊 $u \rightarrow v$，記 $G[u][v]=1$，否則 $G[u][v]=0$。若 $u \rightarrow v$ 有邊權 $w$，可記 $G[u][v] = w$。
```cpp
const int N = 1e3; // 該題測資中，最多 N 個節點
int n; // |V| = n
int G[N][N]; // 若 G[i][j] = 1, 代表 i -> j
```
加入一條邊 `u -> v` ：
```cpp
G[u][v] = 1;
```
遍歷 `u` 的相鄰節點，複雜度：
```cpp
for (int v = 1; v<=n; v++){
if (G[u][v] == 1){
// do something...
}
}
```
實際存法可以依照需求調整，例如若有 $u \rightarrow v$ 且邊權為 $w$，記 $G[u][v]=w$；否則 $G[u][v] = INF$。
### 鄰接串列
用一個陣列 $G$ 表示圖， $G[u]$ 為所有和 $u$ 相鄰的點。通常 $G[u]$ 為一個可變長度陣列，實作上使用 `vector`。
```cpp
const int N = 1e5; // 該題測資中，最多 N 個節點
int n; // |V| = n
vector<int> G[N]; // G[i] 為一 vector，vetor 當中儲存所有和 i 相鄰的節點
```
加入一條邊 `u -> v` ：
```cpp
G[u].push_back(v);
```
遍歷 `u` 的相鄰節點：
```cpp
for (auto v: G[u]){
// do something...
}
```
### 直接存邊
直接將每一條邊的儲存在陣列裡。
```cpp
struct Edge {
int u, v; // u -> v
};
vector<Edge> e;
```
加入一條邊 `u -> v` ：
```cpp
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 的核心精神：盡可能的探索一條分支，可以簡單地用遞迴來實作：
```cpp
vector<int> G[N];
int vis[N];
```
```cpp
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 的演算法概念如下：
```cpp
將起點加入回合 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 的實作範例：
```cpp
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](https://tioj.ck.tp.edu.tw/problems/1209)
- [TIOJ 1081](https://tioj.ck.tp.edu.tw/problems/1081)
- [TIOJ 2062](https://tioj.ck.tp.edu.tw/problems/2062)
- [TIOJ 1099](https://tioj.ck.tp.edu.tw/problems/1099)
- [CF 370A](https://codeforces.com/problemset/problem/370/A)
- [CF 1549B](https://codeforces.com/problemset/problem/1549/B)
## 四、樹
「無根樹」為無向圖的一個特例。當一個連通無向圖沒有環，便稱「樹」。無根樹還有以下的性質，並且這些性質同時可以為樹的定義：
- 有 $n$ 個節點， $n-1$ 條邊的連通圖
- 任兩節點間有恰一條簡單路徑
- 沒有環，並且在加入邊 $(u,v), u≠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[]$ 陣列確保每個節點只會被造訪到一次，在樹當中則只要不往父節點走，就可以避免造訪到重複節點，因為剩下的節點一定是子節點、沒有被造訪過。
```cpp
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$
由於基底在根節點處，我們需要從自己把答案推廣至子節點。範例程式碼如下：
```cpp
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$ 為所有葉節點
由於基底在葉節點處，我們必須要從子節點的答案求出自己的答案：
```cpp
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]$ 便是答案。
```cpp
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](https://cses.fi/problemset/task/1674)
- [Luogu 1352](https://www.luogu.com.cn/problem/P1352)
- [TCIRCOJ. d115](https://judge.tcirc.tw/ShowProblem?problemid=d115)
- [TCIRCOJ. d025](https://judge.tcirc.tw/ShowProblem?problemid=d025)
## 五、有向無環圖
有向無環圖（Directed acyclic graph），故名思義，為無環的有向圖。有向無環圖和樹一樣，都是重要的特例。圖上許多的問題在 DAG 和樹上，都會有更好、更優雅或更簡單的演算法。
DAG 一重要特性，就是在 DAG 上可以 DP。考慮 $u \rightarrow v$， $v$ 為 $u$ 的轉移來源，若圖中有環則會造成循環依賴；反之在 DAG 上，可以順利完成 DP，而出度為 0 的節點便是 DP 中的「基底」（不必遞迴求的狀態）。
而若將 DP 的不同狀態，都當成一個節點，轉移視為有向邊，那也會形成一張 DAG。
### 拓樸排序
拓樸排序的定義：有一張有向圖 $G$，求一個節點到排序，使得若有有向邊 $u \rightarrow v$，則 $u$ 在 $v$ 之前。考慮以下問題：
> 有 $n$ 堂課，每堂課都可能必須先修某些課後才能修。請找出任一種合法的修課順序，使得每堂課修到恰一次。
>
我們可以把每堂課當做一個節點，而當修 $v$ 前，必須先修 $u$，則我們建一條邊 $u \rightarrow 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 \rightarrow v$，我們做 $ind[v]--$。若此時 $ind[v]=0$，則將 $v$ 也加入帶移除的行列。
```cpp
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。
```cpp
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](https://cses.fi/problemset/task/1681)
- [CF 510C](https://codeforces.com/problemset/problem/510/C)
- [ZJ a454](https://zerojudge.tw/ShowProblem?problemid=a454)
Sign in with Wallet
Connect another wallet