---
tags: 成大高階競技程式設計 2021
---
# 2021 Week5 - Basics of Graph
註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。
---
圖論（grpah theory）在資料結構與演算法中，可說是一大主題，
本篇將介紹一些圖（grpah）的基本知識與術語。
# 圖（Graph）
圖（graph），是點（vertex）與邊（edge）的集合；
點是圖的基本元素，而邊描述點之間的關係。
```graphviz
graph {
rankdir=RL;
node [shape=circle, label=""];
A -- B;
A -- C;
B -- C;
B -- E;
C -- D;
D -- E;
D -- F;
}
```
* **點／節點（vertex）**
* 圖的基本元素
* **邊（edge）**
* 點與點的關係
* 鄰點／鄰居（neighbors）
* 透過一條邊直接相連的點
</br>
* 道路（walk）
* 點邊相間的序列（e.g., $v_0e_1v_1e_2v_2\dots e_nv_n$）
* 行跡（trail）
* 邊不重複的道路
* **路徑（path）**
* **點不重複**的道路
* **環（cycle）**
* 只有起點與終點重複的行跡
</br>
* 度數（degree）
* 與點連接的邊數
* 入度（in-degree）
* 點作為終點的邊數
* 出度（out-degree）
* 點作為起點的邊數
</br>
* 連通（connected）
* 點
* 二個點之間有路徑
* 圖
* 任意二點之間連通
* 非連通（disconnected）
</br>
* **（無向）圖（(undirected) graph）**
* 邊無方向性，或說是**雙向**的
* **有向圖（directed graph）**
* 邊有**方向性**
* **賦權圖（weighted graph）**
* 邊有權重
* 二分圖
* 點可以分為二個集合 $X,Y$，所有邊都是 $X$ 到 $Y$ 或 $Y$ 到 $X$
* 完全圖
* 任意二點間都有邊
圖論常用 **$V$** 代表**點集合**，**$E$** 代表**邊集合。**
<hr class="dashed">
## 圖的資料結構
### 鄰接矩陣（Adjacency matrix）
```graphviz
graph {
Adj [shape=none, label=
<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="10">
<TR>
<TD BGCOLOR="DimGray"></TD>
<TD BGCOLOR="DimGray"></TD>
<TD></TD>
<TD BGCOLOR="DimGray"></TD>
</TR>
<TR>
<TD BGCOLOR="DimGray"></TD>
<TD BGCOLOR="DimGray"></TD>
<TD></TD>
<TD></TD>
</TR>
<TR>
<TD></TD>
<TD></TD>
<TD BGCOLOR="DimGray"></TD>
<TD></TD>
</TR>
<TR>
<TD BGCOLOR="DimGray"></TD>
<TD COLSPAN="1"></TD>
<TD></TD>
<TD BGCOLOR="DimGray"></TD>
</TR>
</TABLE>>
];
}
```
用一個二維的矩陣 $adj$，$adj[u][v]$ 代表邊 $(u,v)$，
可能是 `true`, `false` 代表邊存在與否，或是儲存邊的權重。
```cpp!
int n, m; // 點數，邊數
cin >> n >> m;
vector<vector<int>> adj(n, vector<int>(n, false));
while (m--) {
int u, v;
cin >> u >> v;
adj[u][v] = adj[v][u] = true; // 無向圖
}
```
空間複雜度 $O(|V|^2)$。
> 好處是可以快速存取到某條邊。
<hr class="dotted">
### 鄰接表（Adjacency list）
```graphviz
digraph {
rankdir=LR;
V [shape=record, height=2.4, label="<1>1|<2>2|<3>3|<4>4"]
1 [shape=record, width=0.5, label="{3}"];
2 [shape=record, width=1.0, label="{3|4}"];
3 [shape=record, width=1.5, label="{1|2|4}"];
4 [shape=record, width=1.0, label="{2|3}"];
V:1 -> 1;
V:2 -> 2;
V:3 -> 3;
V:4 -> 4;
}
```
並不是任意二點之間都有邊，因此可以只記錄存在的邊，
以起點的角度，$(u,v)$ 把它存到 $u$ 之下。
> 也可以從終點的角度進行紀錄，取決於後續操作的需求。
```cpp!
int n, m; // 點數，邊數
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w); // 賦權有向圖
}
```
空間複雜度 $O(|V| + |E|)$。
> 好處是只遍歷存在的邊，壞處則是比較難找特定的邊，
> 當然真的有需要查詢的話，也可用 `vector<set<int>>` 來記錄。
> 一般**鄰接表較常被使用**，避免無謂的儲存空間與執行時間浪費；
> 完全圖（或稠密圖（dense graph）[^dg]）才比較會使用鄰接矩陣。
<hr class="dashed">
## 圖的遍歷（Graph Traversal）
圖的遍歷也被稱為圖的搜尋（Graph Search），
是指拜訪（visit）圖上各個點的一個過程。
> 不一定要拜訪所有點，工作完成就可以提早結束。
```graphviz
graph {
node [shape=circle, label="", fixedsize=true];
a -- e;
a -- b;
b -- c;
c -- d -- b;
c -- e;
c -- f;
b -- g;
b -- h -- a;
h -- i -- b;
h -- j;
a -- k;
k -- l;
a -- m;
m -- n;
m -- o -- a;
}
```
<hr class="dotted">
### 深度優先搜尋（DFS, Depth-First Search）
顧名思義，要盡量先往深層的地方搜尋，
每次都繼續往鄰點拜訪下去（除非遇到拜訪過的點）。
> 以 $1$ 為根進行 DFS，點上數字代表拜訪順序。
```graphviz
graph {
node [shape=circle, fixedsize=true];
edge [dir=forward, style=bold, color="#8B0000"];
1 -- 2;
3 -- 5 -- 6;
3 -- 2 [dir=back];
3 -- 4;
6 -- 10;
8 -- 7 [dir=back];
6 -- 7;
8 -- 9;
1 -- 11;
11 -- 12;
1 -- 13;
13 -- 14;
13 -- 15;
edge [dir=none, style="", color=black];
1 -- 6;
6 -- 3;
6 -- 8;
8 -- 1;
15 -- 1;
}
```
DFS 走訪的邊，形成一棵[有根樹](#有根樹（Rooted-Tree）)，稱為 **DFS 樹**。
```graphviz
digraph {
node [shape=circle, fixedsize=true];
edge [color="#8B0000"];
1 -> 2;
2 -> 3;
3 -> 4;
3 -> 5;
5 -> 6;
6 -> 7 -> 8 -> 9;
6 -> 10;
1 -> 11;
11 -> 12;
1 -> 13;
13 -> 14;
13 -> 15;
}
```
<hr class="thin">
DFS 過程中，點會有三種狀態：
* 未拜訪
* 拜訪中
* DFS 樹中的子孫尚未拜訪完
* 函數尚在呼叫堆疊（Call stack）中
* 拜訪完
* DFS 樹中的所有子孫都已拜訪完
* 函數已結束
> **拜訪中與拜訪完都稱為已被拜訪。**
```cpp
void dfs(int u, int dep = 0) {
vis[u] = true;
for (auto& v : adj[u]) {
if (vis[v]) continue;
dfs(v, dep + 1);
}
}
```
> * dep：節點深度
> * vis：是否已被拜訪
> * adj：鄰接表
```cpp
dfs(root);
```
<hr class="thin">
> 非連通圖的話，只跑一次 DFS 沒辦法遍歷所有點。
>
> ```cpp!
> for (int i{0}; i < n; ++i)
> if (!vis[i]) dfs(i);
> ```
每個點都被拜訪一次，而每個點都要檢查所有的鄰點（邊），複雜度 $O(|V|+|E|)$。
<hr class="dotted">
### 暴力搜尋
DFS 不只能運用在圖上，一些問題也能透過 DFS 進行暴力搜尋，
而 DFS 本身就有著可以回溯（backtracking）的特性，
所以能夠輕易地知道從初始狀態到答案的過程。
> 回溯就是透過回到父節點，或者說實作上的遞迴返回。
<hr class="thin">
### [Transformation: from A to B](https://codeforces.com/contest/727/problem/A)
:::info
將一個數字，每次乘上 $2$，或是乘以 $10$ 再加 $1$，
請問如何透過若干次操作，將 $a$ 變為 $b$？（或指出這樣是不可能的）
:::
因為二種操作都是指數增長，很快 $a$ 就會大於等於 $b$ 了，
所以可以將所有可能的情況都搜尋一次。
```cpp!
optional<vector<long long>> dfs(long long a, long long b) {
if (a > b) return nullopt;
if (a == b) return vector<long long>{a};
auto r{dfs(a * 10 + 1, b)};
if (r) return r.value().push_back(a), r;
r = dfs(a * 2, b);
if (r) return r.value().push_back(a), r;
return nullopt; // a 無法變為 b
}
```
<hr class="thin">
有時候透過問題特性，知道繼續搜尋下去也找不到答案，
可以提早返回，這樣的技巧稱為「**（暴力）剪枝**」；
不太會降低複雜度，卻有機會能大幅減少執行時間。
<hr class="dotted">
### 廣度優先搜尋（BFS, Breadth-First Search）
顧名思義，要盡量以寬廣的方式搜尋，
將距離搜尋起點較近的點拜訪完後，才去拜訪較遠的點。
```graphviz
graph {
node [shape=circle, fixedsize=true];
edge [dir=forward, style=bold, color="#8B0000"];
1 -- 2;
1 -- 3;
3 -- 10;
8 -- 2 [dir=back];
8 -- 15;
3 -- 9;
1 -- 4;
3 -- 11;
4 -- 12;
1 -- 5;
5 -- 13;
1 -- 6;
6 -- 14;
1 -- 7;
edge[dir=none, style="", color=black];
3 -- 8;
8 -- 10;
3 -- 4;
4 -- 11;
6 -- 7;
}
```
BFS 經過的邊也是形成一棵[樹](#有根樹（Rooted-Tree）)，稱為 **BFS 樹**，
同一深度的節點都拜訪完，才會拜訪到更深的節點。
```graphviz
digraph {
node [shape=circle, fixedsize=true];
subgraph cluster_0 {
style=dotted;
1;
node [style=invis];
A0, B0, C0, D0, E0, F0;
}
subgraph cluster_1 {
style=dotted;
2; 3; 4; 5; 6; 7;
node [style=invis];
A1;
}
subgraph cluster_2 {
style=dotted;
8; 9; 10; 11; 12; 13; 14;
}
subgraph cluster_3 {
style=dotted;
15;
node [style=invis];
A3, B3, C3, D3, E3, F3;
}
edge [style="invis"];
A0 -> A1 -> 8 -> 15;
B0 -> 2 -> 9 -> A3;
C0 -> 3 -> 10 -> B3;
1 -> 4 -> 11 -> C3;
D0 -> 5 -> 12 -> D3;
E0 -> 6 -> 13 -> E3;
F0 -> 7 -> 14 -> F3;
edge [style="", color="#8B0000"];
1 -> 2;
1 -> 3;
1 -> 4;
1 -> 5;
1 -> 6;
1 -> 7;
2 -> 8;
3 -> 9;
3 -> 10;
3 -> 11;
4 -> 12;
5 -> 13;
6 -> 14;
8 -> 15;
}
```
<hr class="thin">
1. 將起點加入佇列（queue）中
2. 每次將一個拜訪中的點 $u$ 取出拜訪，並把 $u$ 所有**未拜訪的鄰點**加進佇列中等待
3. 重複步驟 $2$ 直到佇列為空
過程中，點一樣有三種狀態：
* 未拜訪
* 未進入佇列
* 拜訪中
* BFS 樹中的子節點尚未拜訪
* 在佇列中
* 拜訪完
* BFS 樹中的子節點已被拜訪
* 已離開佇列
```cpp!
void bfs(int u) {
queue<int> qu{};
qu.push(u), vis[u] = true;
while (!qu.empty()) {
u = qu.front(), qu.pop();
for (auto& v : adj[u]) {
if (vis[v]) continue;
qu.push(v), vis[v] = true;
}
}
}
```
> 若是非聯通圖，一次 BFS 也沒辦法拜訪完所有點。
複雜度與 DFS 相同，為 $O(|V|+|E|)$。
<hr class="dotted">
### 最短路徑（無權重）
搜索圖上**起點到任意點**的最短路徑，就很適合 BFS，
因為它先拜訪完距離近的點，才慢慢往距離遠的點拜訪。
尤其在二維矩陣上，可以直接執行 BFS，也不需要真的有一個圖。
* 牆（不能走）：`*`
* 路：` `
* 起點：`@`
* 終點：`#`
```
* * * * * * * * * *
* * * * @ * *
* * * * *
* * * * * * *
* * * * *
* * * * *
* * * * *
* * * *
* * * * *
* * * * * *
* # * * *
* * * * * * * * * *
```
數字代表距離（BFS 樹的深度）。
```haskell
* * * * * * * * * *
* * * * 1 0 1 2 * *
* 5 4 3 2 * * 3 * *
* 6 * 4 * * * 4 * *
* 7 * 5 6 7 * 5 * *
* 8 * 6 * 8 7 6 * *
* 9 10 * * 9 * 7 8 *
* * 11 12 11 10 * * 9 *
* * * 12 * 12 11 10 *
* * * 13 * 13 * 11 *
* 17 16 15 14 15 14 * * *
* * * * * * * * * *
```
<hr class="thin">
### [Fire!](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2671)
:::info
在一個矩陣上，有 Joe 與好幾個起火點，`#` 代表牆，`.` 代表路。
Joe 每分鐘可以往上下左右移動一格，火則是每分鐘會往四個方向擴散一格，
請問 Joe 能夠順利逃出這個矩陣範圍嗎？可以的話要多久呢？
:::
```cpp!
int R, C;
cin >> R >> C;
vector<vector<int>> maze(R, vector<int>(C));
pair<int, int> J;
vector<pair<int, int>> F{};
for (int r{0}; r < R; ++r)
for (int c{0}; c < C; ++c) {
char x;
cin >> x;
if (x == 'J') J = {r, c};
if (x == 'F') F.emplace_back(r, c);
maze[r][c] = (x == '#' ? -1 : R + C);
// 先給一個夠大的數，代表走不到
}
```
Joe 不能被火燒到，所以 Joe 一定要**走得比火快**，
因此，先算出火何時會燒到各個點（搜尋火源到各點的**最短路徑**）。
```cpp!
/* 上,下,左,右 */
const array<int, 4> dr{-1, 1, 0, 0};
const array<int, 4> dc{0, 0, -1, 1};
vector<vector<bool>> vis(R, vector<bool>(C, false));
queue<pair<int, int>> qu{};
for (auto& f : F) {
maze[f.first][f.second] = 0;
vis[f.first][f.second] = true;
qu.push(f);
}
while (!qu.empty()) {
auto [r, c]{qu.front()}; qu.pop();
for (int d{0}; d < 4; ++d) {
int nr{r + dr[d]}, nc{c + dc[d]};
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; // 超出邊界
if (maze[nr][nc] == -1 || vis[nr][nc]) continue; // 牆壁 or 走過的點
maze[nr][nc] = maze[r][c] + 1;
vis[nr][nc] = true;
qu.emplace(nr, nc);
}
}
```
現在已經計算完火到各個點的時間了，
接著就可以讓 Joe 也找一次最短路徑，
除了牆壁不能走以外，火更早抵達的點也不能走。
```cpp
for (int r{0}; r < R; ++r) fill(vis[r].begin(), vis[r].end(), false);
// 重複使用 vis，先初始化一下
maze[J.first][J.second] = 0;
// 因為火源與 Joe 不在同個點上，所以至少 Joe 一開始是安全的
vis[J.first][J.second] = true;
qu.push(J);
while (!qu.empty()) {
auto [r, c]{qu.front()}; qu.pop();
for (int d{0}; d < 4; ++d) {
int nr{r + dr[d]}, nc{c + dc[d]};
if (nr < 0 || nr >= R || nc < 0 || nc >= C) { // 逃出邊界
cout << maze[r][c] + 1 << '\n';
return ;
}
if (maze[nr][nc] == -1 || vis[nr][nc]) continue; // 牆壁 or 走過的點
if (maze[nr][nc] <= maze[r][c] + 1) continue; // 火先到達的點
maze[nr][nc] = maze[r][c] + 1;
vis[nr][nc] = true;
qu.emplace(nr, nc);
}
}
cout << "IMPOSSIBLE\n"s;
```
如果能走出邊界，Joe 就順利逃脫啦！
---
# 樹（Tree）
樹是一個連通無環無向圖（connected acyclic undirected graph）。
```graphviz
graph {
node [shape=circle, label=""];
A -- B;
A -- C;
A -- D;
B -- E;
B -- F;
}
```
<hr class="dashed">
## 有根樹（Rooted Tree）
> 有根樹很常見，但通常不會強調「有根」，請依情境判斷；
> 而「樹」在處理時，常常也會選擇一個點作為根，例如 DFS 或 BFS。
有根樹（rooted tree）是一棵一個節點被指定為根（root）的樹，
如此一來樹就有方向（orientation），像一棵倒著的[樹](https://en.wikipedia.org/wiki/Tree)。
> 方向可以是遠離根，也可以是指向根。
```graphviz
digraph {
node [shape=circle, label=""];
A [label="R"];
A -> B;
A -> C;
A -> D;
B -> E;
B -> F;
a [label="R"];
a -> b [dir=back];
a -> c [dir=back];
a -> d [dir=back];
b -> e [dir=back];
b -> f [dir=back];
}
```
* **節點（node）**
* 樹的基本元素
* **根（root）**
* **父節點（parent）**
* 靠近根的鄰點
* **子節點（child）**
* 遠離根的鄰點
* 祖先（ancestor）
* 往父節點移動多次可以到達的節點
* 子孫（descendant）
* 往子節點移動多次可以到達的節點
* **葉（leaf）**
* 沒有子節點的節點
</br>
* 高度（height）
* 節點高度（height of a node）
* 往下到某個葉的最長距離
* 樹高度（height of the tree）
* 根的高度
* 深度（depth）
* 節點深度（depth of a node）
* 到根的距離
</br>
* 子樹（subtree）
* 以某節點 $u$ 為根，包含 $u$ 所有的子孫而形成的樹
* 森林（forest）
* 多棵不相交（disjoint）的樹形成的集合
<hr class="dotted">
## 二元樹
```graphviz
graph {
node [shape=circle, label=""];
A :sw -- B;
B :sw -- D;
B :se -- E;
A :se -- C;
C :se -- F;
F :sw -- G;
F :se -- H;
}
```
每個節點**至多有二個子節點**的有根樹，稱為二元樹；
二個子節點分別稱為左子節點（left child）與右子節點（right child）。
<hr class="thin">
> 深度相同的節點稱為同一層。
**二元樹中，深度為 $d$ 的節點數最多 $2^d$ 個。**
> 1. $d=0$ 時成立。
> 2. 若 $d=k$ 時，節點數不超過 $2^k$，
> 則 $d=k+1$ 時，節點數不超過 $2\cdot2^k$。
>
> 根據數學歸納法，命題為真。
**樹高為 $h$ 的二元樹，節點數不超過 $2^{h+1}-1$。**
> $1+2+...+2^h=2^{h+1}-1$
<hr class="thin">
* 完美二元樹（perfect binary tree）
* 每一層的節點都是滿的
> ```graphviz
> graph {
> node [shape=circle, label=""];
>
> A :sw -- B;
> B :sw -- C;
> B :se -- D;
> A :se -- E;
> E :sw -- F;
> E :se -- G;
> }
> ```
* 完全二元樹（complete binary tree）
* 除了最底層以外，其餘的節點是滿的，並且最底層的節點也是靠左填滿的
> ```graphviz
> graph {
> node [shape=circle, label=""];
>
> A :sw -- B;
> B :sw -- C;
> B :se -- D;
> A :se -- E;
> E :sw -- F;
> G [style=invis];
> E :se -- G [style=invis];
> }
> ```
<hr class="thin">
對於完全二元樹，我們可以用編碼的方式，將其儲存於陣列之中。
```graphviz
graph {
node [shape=circle];
1 :sw -- 2;
2 :sw -- 4;
2 :se -- 5;
1 :se -- 3;
3 :sw -- 6;
7 [style=invis];
3 :se -- 7 [style=invis];
}
```
如果由上至下，由左至右進行編號，
**編號為 $v$ 的節點，左子節點編號為 $2v$，右子節點編號為 $2v+1$。**
> 1. 當 $v=1$ 時，命題為真。
> 2. 如果 $v=k$ 時命題也為真，
> 因為 $k+1$ 的左子節點緊隨在 $k$ 的右子節點後面，
> 編號為 $2k+2$，而右子節點編號為 $2k+3$，命題也為真。
>
> 根據數學歸納法，對任意數命題都為真。
<hr class="dashed">
## 樹的資料結構
樹是圖的一種，可以用鄰接表儲存；
為了動態加入與刪除節點，也可以用指標的方式來儲存。
```cpp!
struct Node {
Node* p;
vector<Node*> ch;
// 其他資料
};
```
<hr class="dashed">
## 樹的性質
```graphviz
graph {
rankdir=LR;
node [shape=circle, fixedsize=true, label=""];
6 [style=filled];
1 -- 2 -- 5;
3 -- 4 -- 5 -- 6 [style=bold];
6 -- 7 -- 8;
7 -- 9;
5 -- 10 -- 11;
5 -- 12;
5 -- 13;
14 -- 5;
}
```
> 這裡討論的是樹，不是有根樹。
#### 葉（leaf）
度數為 $1$ 的點。
#### 離心率（Eccentricity）
點 $u$ 的離心率，定義為 $u$ 到其他點的最長距離。
<hr class="dotted">
### 樹的中心（Centers of a tree）
中心是**離心率最小**的點。
對於任意點數大於 $2$ 的樹，所有的葉都不會是中心。
> 假設點 $u$ 是葉，$v$ 是它唯一相鄰的點，$u$ 到其他點 $w$ 的距離 $d(u, w) = d(v,w) + 1$，
> $u$ 的離心率大於 $v$，所以 $u$ 不是中心。
任意點 $u$ 到其他點的最長路徑，終點一定是葉，
所以**把所有的葉移除**後，所有非葉的點離心率會減 $1$，
並且**中心不變**。
因此要尋找中心的話，只需要持續把葉移除，直到剩餘 $1$ 或 $2$ 個點。
> **樹的中心只有 $1$ 或 $2$ 個**；如果有 $2$ 個中心，彼此相鄰。
```cpp!
pair<int, int> center(const vector<vector<int>>& adj) {
int n{adj.size()};
vector<int> d(n); // degree
vector<int> leaf{};
for (int u{0}; u < n; ++u) {
d[u] = adj[u].size();
if (d[u] == 1) leaf.push_back(u);
}
int ts{n}; // tree size
while (ts > 2) {
vector<int> nl{};
ts -= leaf.size();
for (auto& u : leaf)
for (auto& v : adj[u])
if (--d[v] == 1) nl.push_back(v);
leaf.swap(nl);
}
return {leaf[0], leaf.size() == 2 ? leaf[1] : -1};
}
```
<hr class="dotted">
### 樹的半徑（Radius of a tree）
半徑是**中心為起點的最長路徑**；半徑（長度）是中心的離心率。
> 找中心時，移除了葉幾次，就可以知道半徑長度；
> 以中心為根，進行 DFS 也可以找出半徑。
<hr class="dotted">
### 樹的直徑（Diameter of a tree）
直徑是樹上**最長路徑**；直徑（長度）是所有點的離心率的最大值。
一條最長的路徑在 DFS 樹會有一個深度最小的點，
所以路徑就可以分為此點往子樹最長的二條路徑。
> 也有可能只有一棵子樹。
```cpp!
int dfs(int u, int w = -1) {
int mx{0};
for (auto& v : adj[u])
if (v != w) {
auto len{1 + dfs(v, u)};
diam = max(diam, mx + len);
// 二條路徑透過 u 接在一起
mx = max(mx, len);
}
return mx;
}
```
> 如果要真的找出路徑，紀錄每個節點最長與第二長的路徑，是往哪個子節點，
> 並紀錄到底哪個點，是直徑在 DFS 樹中深度最小的點。
<hr class="dotted">
### 關聯（Relationship）:bulb:
> 令 $D$ 為直徑長度，$R$ 為半徑長度。
中心 $c$，假設某鄰點 $x$，$c$ 往 $x$ 走到 $y$ 為半徑，
至少還有另外一鄰點 $a$，$c$ 往 $a$ 走到某個葉 $b$，$d(c,b)\ge R-1$。
:::spoiler 證明
> ```graphviz
> graph {
> rankdir=LR;
> node [shape=circle];
> n0 [style=dotted, label=""];
> n1 [style=dotted, label=""];
> n2 [style=dotted, label=""];
>
> c -- x -- n0;
> n0 -- n1 -- y [style=dotted];
> c -- a -- n2;
> n2 -- b [style=dotted];
> }
> ```
>
> 以 $c$ 為根，在子樹 $x$ 這邊的節點 $u$，$d(x,u)=d(c,u)-1$；
> 而其餘節點 $v$，$d(x,v)=d(c,v)+1$。
> 如果 $d(c,v)$ 都小於 $R-1$，則 $d(x,v)\le R-1$，
> $x$ 的離心率只有 $R-1$，與 $c$ 是中心矛盾，所以假設錯誤。
>
> > 從找中心的過程，因為 $c$ 的度數一直大於 $1$，也可以得到相同結論。
:::
<hr class="thin">
通過中心的最長路徑至少 $2R-1$，代表直徑的下界；
而直徑的上界為 $2R$，若是大於 $2R$，沒有點的離心率會等於 $R$。
如果 $D=2R$，只有一個點的離心率能夠等於 $R$，所以只有一個中心；
若 $D=2R-1$，則有二個相鄰的點離心率都是 $R$，有二個中心。
:::danger
**若只有 $1$ 個中心，$D=2R$；若有 $2$ 個中心，$D=2R-1$**；並且中心在直徑上。
:::
<hr class="dotted">
### 樹的重心（Centroids of a tree）
以某個點為根，其**最大子樹最小的點**，即為重心。
進行 DFS 的時候，對於某一點 $u$，除了 DFS 樹上的所有子樹外，
還有往父節點的也是子樹，大小可以由其他子樹的節點數推算。
```cpp!
int n;
vector<int> mxst(n, 0); // max subtree
int dfs(int u, int w = -1) {
int sz{1}; // u 與所有子樹的節點數量
for (auto& v : adj[u])
if (v != w) {
int s{dfs(v, u)};
mxst[u] = max(mxst[u], s);
sz += s;
}
mxst[u] = max(mxst[u], n - sz); // 往父節點的子樹
return sz;
}
```
**樹最多有二個重心。**
:::spoiler 證明
> 令 $s$ 為重心的最大子樹大小；
> 如果有三個點 $x,y,z$ 都是重心，$y$ 在 $x\to z$ 的路徑上；
> 對 $y$ 來說，如果 $z$ 所在子樹大小為 $s$，
> 則 $x$ 的最大子樹大於 $s$，$x$ 不會是重心；
> 如果 $x$ 所在子樹大小為 $s$，$y$ 不會是重心；
> 如果有另一棵子樹大小為 $s$，而且 $x,z$ 都不在其中，$x,z$ 都不是重心。
:::
<hr class="dashed">
## 並查集（Disjoint Set Union-Find Forest, DSU）
**對於不交集的集合（Disjoint Set），支援合併與查詢。**
利用樹狀結構來記錄，**一棵樹代表一個集合**；
**合併**，只需將二個樹合在一起，最簡單的就是把**根接到另一棵樹的根上**；
而**查詢**，只需**找到樹根**，用根的編號代表該集合，就能讓每個集合有一個獨特（unique）的編號。
一開始每個元素都是一個獨立的集合。
```graphviz
graph {
0; 1; 2; 3; 4;
}
```
<hr class="dotted">
### Weighted Union
```graphviz
graph {
0; 1; 2; 3; 4;
2 -- 3;
}
```
如果 $\{2,3\}$ 再跟 $\{0\}$ 合併，由 $0$ 當根的話，樹高會變得更高。
```graphviz
graph {
0; 1; 2; 3; 4;
0 -- 2 -- 3;
}
```
所以透過集合的大小來決定誰當根，可以將樹高限制在 $O(\lfloor\log_2 n\rfloor)$。
```graphviz
graph {
0; 1; 2; 3; 4;
2 -- 0;
2 -- 3;
}
```
> #### 證明
> 1. $n=1$ 時，命題成立。
> 2. 假設二個集合個數為 $n_1,n_2$，高度為 $h_1,h_2$ 並符合命題，
> 不失一般性假設 $n_1\ge n_2$，合併之後樹高為 $\max(h_1,h_2+1)$，
> 則合併後的樹也符合命題。
> * $\lfloor\log_2(n_1+n_2)\rfloor\ge\lfloor\log_2n_1\rfloor\ge h_1$
> * $\lfloor\log_2(n_1+n_2)\rfloor\ge \lfloor\log_2(2n_2)\rfloor=\lfloor \log_2(n_2) \rfloor+1\ge h_2+1$
>
> 根據數學歸納法，命題成立。
<hr class="dotted">
### Collapsing Find
每次查詢的過程，都要一直往父節點尋找找，而所有祖先一樣都在這個集合之中，
所以就可以將他們都接到根下，縮小節點深度，避免下次查詢重複計算。
```graphviz
graph {
1 [style=filled];
6 -- 2 [dir=back];
2 -- 0 [dir=back];
0 -- 1 [dir=back];
1 -- 4;
1 -- 5;
2 -- 3;
}
```
> 查詢後：
> ```graphviz
> graph {
> 6 -- 0;
> 6 -- 1;
> 1 -- 4;
> 1 -- 5;
> 6 -- 2;
> 2 -- 3;
> }
> ```
<hr class="dotted">
### Implementation
不管合併或查詢，都只會往父節點的方向移動，所以用一個陣列 $p$ 來記錄父節點就足夠了。
> 根的父節點可以設定為 `-1`，或是根自己。
> `find()` 在遞迴返回得知根結點後，才能把路徑上的點的父節點也都設為根結點。
```cpp!
// fast disjoint set union
class DSU {
vector<int> p, sz;
public:
explicit DSU(int n) : p(n, -1), sz(n, 1) {}
int find(int x) { // collapsing find
return p[x] == -1 ? x : p[x] = find(p[x]);
}
void unionn(int x, int y) { // weighted union
auto rx{find(x)}, ry{find(y)};
if (rx == ry) return ;
if (sz[rx] < sz[ry]) swap(rx, ry);
p[ry] = rx, sz[rx] += sz[ry];
}
};
```
Weighted Union 搭配 Collapsing Find，均攤複雜度為 $\alpha(n)$，
是個成長非常緩慢的函數，inverse Ackermann function，在實務上不超過 $5$，
可以**將並查集的操作視為均攤常數時間**（amortized constant time）。
> 複雜度分析過於錯綜複雜，就不討論。
<hr class="thin">
:bulb::bulb::bulb:有一個較簡單的分析[^DSU]，可以得出複雜度上界為 $O(\lg^*n)$。
> In computer science, $\lg^*$ is often used to indicate the binary iterated logarithm.[^itlog]
:::spoiler
定義一個節點 $u$ 的大小，
如果 $u$ 是根，$u$ 的大小為樹的節點數；
如果不是根，$u$ 的大小為最後為根時的大小。
> 與程式碼中的 `size` 一致。
> :::danger
> （推論 1.）節點 $u$ 的大小為 $s$， 父節點的大小至少為 $2s$。
> :::
將結點依照大小分籃，$[1:2),[2:4),[4:16),[16:65536),\dots$，
如果某一籃的範圍是 $[2^B:2^{2^B})$，下一籃的範圍是 $[2^{2^B}:2^{2^{2^B}})$。
> :::danger
> （推論 2.）籃子數為 $\log^*n$。
> :::
> :::danger
> （推論 3.）籃子 $[2^B:2^{2^B})$ 中的元素不多於 $2n/2^B$ 個。
> :::
> 將籃子分隔為 $[2^B:2^{B+1}), [2^{B+1}:2^{B+2})+\dots+[2^{(2^B-1)}:2^{2^B})$，
> 先討論區間 $[2^B:2^{B+1})$，
> 根據推論 1.，區間中元素的祖先與子孫都不在區間中，
> 所以區間中的元素的子節點與曾經的子節點都不重複，
> 因此區間中的元素最多有 $n/2^B$ 個；
> 籃子中其他區間亦同，因此得到結論，籃子中的元素，
> 最多有 $n/2^B+n/2^{B+1}+\dots+n/2^{(2^B-1)}\le2n/2^B$ 個。
<hr class="thin">
$m$ 次 `find()`，將所有一步一步往上找的過程，
依照 $u$ 到父節點 $w$ 的差別分成三類。
1. $w$ 是根
* 每次 `find()` 出現一次，**複雜度為 $O(m)$**。
2. $u,w$ 屬於不同籃子（$w$ 不是根）
* 因為往上找的過程節點大小一直變大，
根據推論 2.，每次 `find()` 最多有 $\log^*n$ 個（籃子數），
**複雜度為 $O(m\lg^*n)$**。
3. $u,w$ 屬於同個籃子 $[2^B:2^{2^B})$（$w$ 不是根）
* 固定某個節點 $u$，根據推論 1.，可以當 $w$ 的最多只有 $2^B$ 個，
而因為 Collapsing Find，這樣的 $(u,w)$ 只會走一次；
根據推論 3.，籃子最多有 $2n/2^B$ 個節點，
所以一個籃子中，最多走 $(2n/2^B)\cdot2^B=2n$ 個這樣的 $(u,w)$；
又根據推論 2.，最多有 $\lg^*n$ 個籃子，**複雜度為 $O(n\lg^*n)$**。
總複雜度為 $O(n+m\lg^*n+n\lg^*n)=O(m\lg^*n)$，
每次操作的**均攤複雜度為 $O(\lg^*n)$**。
> `unionn()` 除了 `find()` 以外是常數時間，所以複雜度相同。
> $m$ 如果小於 $n$，$O(n\lg^*n)$ 也跟初始化的 $O(n)$ 差不多了。
> $\lg^*(2^{65536})=5$
:::
---
# 有向無環圖（DAG, Directed Acyclic Graph）
```graphviz
digraph {
A -> B;
A -> C;
A -> D;
A -> F;
B -> C;
C -> E;
D -> C;
E -> F;
}
```
## 拓樸排序（Topological Sort）
拓樸排序是一個排序，使得**對於任意有向邊 $(u,v)$，$u$ 都在 $v$ 之前；
一個圖有拓樸排序若且唯若它是一個 DAG**。
> ABDCEF 或 ADBCDF 都是一個拓樸排序。
要找到一個拓樸排序也很簡單，
只要持續把入度為 $0$ 的點加入排序中，
接著從圖中移除並更新其他點的入度，
直到處理完所有點，或是找不到拓樸排序為止。
```cpp!
optional<vector<int>> topSort(vector<vector<int>>& adj) {
vector<int> res{};
int n{adj.size()};
vector<int> cnt(n, 0); // 入度
for (int u{0}; u < n; ++u)
for (auto& v : adj[u]) ++cnt[v];
queue<int> qu{};
for (int u{0}; u < n; ++u) if (!cnt[u]) qu.push(u);
// 一開始入度為 0 的點
while (!qu.empty()) {
auto u{qu.front()}; qu.pop();
res.push_back(u);
for (auto& v : adj[u]) if (!--cnt[v]) qu.push(v);
// 入度變為 0 即可放入排序中
}
if (res.size() != adj.size()) return nullopt;
// 不存在拓樸排序
return res;
}
```
---
# References
* Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed (2007). “Fundamentals of Data Structures in C, 2/e”.
* 張鎮華、蔡牧村（2020）。演算法觀點的圖論（修訂版）。
* Wikipedia - [Graph theory](https://en.wikipedia.org/wiki/Graph_theory)
* Wikipedia - [Tree (graph theory)](https://en.wikipedia.org/wiki/Tree_(graph_theory))
* Wikipedia - [Disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
* CP-Algorithms - [Disjoint Set Union](https://cp-algorithms.com/data_structures/disjoint_set_union.html)
* Wikipedia - [Graph traversal](https://en.wikipedia.org/wiki/Graph_traversal)
[^dg]: 稠密圖（dense graph），意指邊數接近上限的圖；與之相對的是稀疏圖（sparse graph）。
[^DSU]: 內容參考自 Wikipedia - [Disjoint-set data structure, Time complexity](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Proof_of_O(log*(n))_time_complexity_of_Union-Find)
[^itlog]: Wikipedia - [Iterated logarithm](https://en.wikipedia.org/wiki/Iterated_logarithm)
---
# 練習題
| Problem | Tags |
|:-:|:- |
| [新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290) | `BFS`, `DFS` |
| [迷宮問題#1](https://zerojudge.tw//ShowProblem?problemid=a982) | `BFS` |
| [00532 - Dungeon Master](https://zerojudge.tw/ShowProblem?problemid=c124) | `BFS` |
| [肥水之戰](https://tioj.ck.tp.edu.tw/problems/1602) | `BFS` |
| [00572 - Oil Deposits](https://zerojudge.tw/ShowProblem?problemid=c129) | `BFS` / `DFS` |
| [圖論 之 二分圖測試](https://tioj.ck.tp.edu.tw/problems/1209) | `BFS` / `DFS` |
| [老闆阿我要退貨](https://zerojudge.tw/ShowProblem?problemid=b298) | `DFS` |
| [一筆畫問題](https://tioj.ck.tp.edu.tw/problems/1084) | `DFS` |
| [第 4 題 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967) | `tree diameter` |
| [黑暗部落](https://zerojudge.tw/ShowProblem?problemid=d808) | `DSU` |
| [APCS 2017-0304-2小群體](https://zerojudge.tw/ShowProblem?problemid=c291) | `DSU` |
| [TOI2010 第二題：專案時程](https://zerojudge.tw/ShowProblem?problemid=a454) | `Topological sort` |
| [Fox And Names](https://codeforces.com/contest/510/problem/C) | `Topological sort` |
| **Challenging** |
| [UVa 1267 - Network](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3708) | |
<style>
hr.thin {
height: 0.5px;
}
hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}
hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}
/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}
/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}
</style>
Sign in with Wallet
Connect another wallet