# 4－基礎圖論
### 108學年度師大附中北市資訊學科能力競賽校內培訓
### joylintp
### 2019年10月31日
---
## 1. 什麼是圖
> 「圖是圖論的主要研究對象。圖是由若干給定的頂點及連接兩頂點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係。頂點用於代表事物，連接兩頂點的邊則用於表示兩個事物間具有這種關係。」
以上是取自維基百科的說明。在資訊的講法上，一張圖$G$（Graph）通常包含著點$V$（Vertex / Node）和邊$E$（Edge）。另外，我們通常會把一條邊$e$表示成$e=(u, v), u, v, \in V$。
### 1.1 圖的分類
* 無向圖（undirect graph）：圖中的任何邊$(u, v)$與$(v, u)$等價，意指你可以從$u$走到$v$也能走回來。
* 有向圖（direct graph）：圖中的邊$(u, v) \neq (v, u)$，通常邊$(u, v)$代表這條邊允許從$u$走到$v$，但不能反向走。
### 1.2 圖論術語
此處說明皆以下圖為無向圖範例。
此處說明皆以下圖為有向圖範例。
* 點數、邊數：以$|V|$和$|E|$表示。為求方便書寫，在寫複雜度時通常以$V$、$E$表示。
有向圖範例中，$|V| = 6, |E| = 8$。
* 權重（weight）：有時候我們會在每一個點和邊附帶一個數稱為「權重」。比較常見的是邊的權重（邊權），通常會作為表達長度或花費時間的方法。
有向圖範例中，邊$(1, 2)$的邊權為2。
* 度（degree）：一個點連接的邊數即稱為這個點的「度」。在有向圖中可細分為「入度（in-degree）」和「出度（out-degree）」，分別表示以這個點為終點和起點的邊的數量。
無向圖範例中，點1的度數為3。
有向圖範例中，點1的入度為1，出度為2。
* 相鄰（adjacent）：無向圖中，兩個點$u, v$相鄰代表存在一條邊$e_i=(u, v)$。
無向圖範例中，點1和點3相鄰，點1和點6不相鄰。
* 指向（consecutive）：有向圖中，$u$指向$v$代表存在一條邊$e_i=(u, v)$。
有向圖範例中，點1指向點2，點2不指向點1。
* 路徑（path）：一個由$u$走到$v$的路徑，可以經由一連串的點由指向或相鄰關係構成。
無向圖範例中，點3到點6存在路徑3→1→2→6。
有向圖範例中，點3到點6存在路徑3→1→2→6，點6到點3不存在路徑。
* 行跡（trace）：一條路徑中所有的邊皆不同，稱為行跡。
無向圖範例中，路徑2→1→4→3→1為行跡。
有向圖範例中，路徑1→4→3→1→2為行跡。
* 簡單路徑（track）：一條路徑中除了起點終點外，所有的點兩兩相異，稱為簡單路徑。
無向圖範例中，路徑2→1→4→3為簡單路徑。
有向圖範例中，路徑1→4→3為簡單路徑。
* 環（cycle）：一條簡單路徑的起終點相同，稱為環。
無向圖範例中，路徑2→1→4→3→1→2為環。
有向圖範例中，路徑1→4→3→1為環。
* 迴路（circuit）：一條行跡的起終點相同，稱為迴路。
無向圖範例中，行跡1→3→4→1為迴路。
有向圖範例中，行跡1→4→3→1為迴路。
* 自環（loop）：一條邊$e_i=(u, v)$滿足$u = v$即稱為自環。
無向圖及有向圖範例中，邊$(4, 4)$為自環。
* 重邊（multiple edge）：在一張圖中，存在$e_i, e_j$滿足$i \neq j$且$e_i = e_j$，則稱為重邊。
無向圖及有向圖範例中，邊$(2, 5)$為重邊。
* 連通（connected）：無向圖中，若$u$和$v$存在路徑，則$u$和$v$連通。若一群點倆倆連通，則這些點都連通。
無向圖範例中，任兩點都連通。
### 1.3 一些特殊的圖
* 簡單圖（simple graph）：圖中不存在自環及重邊即稱為簡單圖。
* 連通圖（connected graph）：在無向圖上，如果任兩個點都可以經由一些邊互相訪問，那這張圖就是連通圖。
* 樹（tree）：一張沒有環且連通的圖稱為一棵樹。
* 森林（forest）：一張由樹棵不連通的樹組成的圖稱為森林。
* 完全圖（complete graph）：無向圖上，對於任何一個點對$(u, v)$，都存在邊$e_i=(u, v)$。一張$n$個點的完全圖通常會以$K_n$簡記之。完全圖在集合上被稱為「團（clique）」。
* 競賽圖（tournament graph）：有向圖上，對於任何一個點對$(u, v)$，都存在邊$e_i=(u, v)$。
* 有向無環圖（directed acyclic graph，簡稱DAG）：沒有環的有向圖稱為一張DAG。
* 二分圖（bipartite graph）：如果你能把這張圖的點分成兩個集合，且對於任何的邊$e_i=(u, v)$都滿足$(u, v)$分別在不同的集合裡，那這張圖即為二分圖。
* 平面圖（planar graph）：可以畫在平面上並且使得不同的邊可以互不交疊的圖。
### 1.4 圖之間的關係
* 子圖（subgraph）：如果兩張圖$G=(V, E)$；$G'=(V', E')$滿足$V' \subseteq V$且$E' \subseteq E$則稱$G'$是$G$的子圖。
* 補圖（complement graph）：令$G=(V, E)$為一張圖，$K$包含所有$V$的二元子集（2-element subset）。則圖$H=(V, K \backslash E)$是$G$的補圖。簡單來說就是若原本的邊消失，原本不存在的邊出現。
* 同構（isomorphic）：如果對於兩張圖$G$、$H$的點集$V(G)$、$V(H)$，存在一個一一對應的函數$f:V(G)\rightarrow V(H)$，使得對於$G$中的任何兩點$v_i$、$v_j$，$v_i$與$v_j$相鄰若且唯若$f(v_i)$與$f(v_j)$相鄰，稱$G$與$H$同構，記為$G ≃ H$。簡單來說就是這兩張圖可以透過重新編號來變成長得一樣的圖。
* 生成樹（spanning tree）：無向圖中，一個樹的子圖稱為一棵生成樹。
## 2. 儲存及遍歷
### 2.1 儲存
* 鄰接矩陣（adjacency matrix）：開一個$V \times V$的資料結構$M$（通常為二維陣列），$M_{a, b}$代表的是點$a$至$b$的邊數或權重。空間複雜度$O(V^2)$，加、刪邊時間複雜度$O(1)$。
* 鄰接串列（adjacency list）：開$V$個可變長度的資料結構（通常為```vector```），第$i$個裡面放所有第$i$個點指向的點的編號和其他資訊。空間複雜度$O(V+E)$，加邊時間複雜度$O(1)$，刪邊時間複雜度$O(V)$。
鄰接串列的好處在於，遍歷圖的時候可以保證不會讀到不必要的資訊，複雜度通常都是$O(V+E)$，空間也相對優秀。其餘情況用鄰接矩陣皆不會比較差。
### 2.2 遍歷
遍歷是指存取圖中資料的方法。
以下的範例程式碼中，我們以鄰接串列```vector<int> G[]```來儲存圖片。
#### 2.2.1 深度優先搜索（depth-first search）
簡稱DFS。找到與當前的節點相鄰的未尋訪節點進行遍歷。若此點沒有新的鹿，則沿原路返回直到到達最近一個與未遍歷過的節點相鄰的節點，再向下遍歷。
以下為遞迴版本的DFS，時間複雜度為$O(V+E)$，額外空間複雜度為$O(V)$。
```cpp=
void dfs(int u)
{
vis[u] = true;
for (int i : G[u])
if (!vis[i])
dfs(i);
}
```
以下為STL```stack```版本的DFS：
```cpp=
while (!stk.empty())
{
int u = stk.top();
stk.pop();
vis[u] = true;
for (int i : G[u])
if (!vis[i])
stk.push(i);
}
```
### 2.2.2 廣度優先搜索（breadth-first search）
簡稱BFS。先遍歷過當前節點的所有相鄰節點，再將這些點的相鄰節點放入待遍歷的佇列中。時間複雜度一樣為$O(V+E)$，額外空間複雜度為$O(V)$。
以下為用```queue```實作的BFS：
```cpp=
while (!quu.empty())
{
int u = quu.front();
quu.pop();
vis[u].true;
for (int i : G[u])
if (!vis[i])
quu.push(i);
}
```
可以發現BFS會先把距離起點為0的點（起點本身）遍歷過，再遍歷距離起點為1的點，再遍歷距離為2的點，依此類推。因此，我們可以用BFS解決邊權相同的最短路徑問題。
:::info
:bulb: 格子圖小技巧
當我們在二維表格上遍歷時，如果用8行程式控制移動的8個方向時會使程式可讀性降低，也提高錯誤率。
我們可以用以下的小技巧來加快寫程式的速度：
```cpp=
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int i = 0; i < 8; i++)
if (chk(x + dx[i], y + dy[i]))
{
cout << x + dx[i] << ' ' << y + dy[i] << '\n';
// 遍歷(x + dx[i], y + dy[i])
}
```
:::
### 2.3 習題
<!--待補-->
## 3. 樹
在圖論中，樹是一種有很多特殊性質的圖，在樹上可以有很多的特別算法和特別的問題。
回顧一下樹的定義：一張沒有環且連通的圖稱為一棵樹。
### 3.1 判斷
對於以下任何一種無向圖的敘述皆是在表示樹，這些敘述也可以當作是判斷一棵樹的方法。
* 連通，且$|V|=|E|+1$。
* 任意兩個點之間存在唯一的簡單路徑。
* 連通，但去掉任意一條邊就不連通。
* 沒有環，但加上任意一條邊就有環。
* 若節點邊號存在一個順序，除了第一個節點，每個節點都伸出一條邊連到順序比自己前面的節點。
這些性質甚至有時候會被當作是解題的關鍵，可以嘗試理解它們。
### 3.2 「樹」相關的術語
此處說明皆以下圖為範例
* 根（root）：樹上一個具代表性的節點。若題目有給定根結點，則稱這棵樹為「有根樹」。根通常會被當成遍歷起點，所以無根樹通常也得找一個節點給它。
此處範例皆以節點1為根結點。
* 葉子（leaf）：在樹上度數只有1的節點稱為葉子，通常如果是有根樹根節點的度數是1的話會獨立不將其視為葉節點，視題目所需。
範例圖中，節點4、5、8、11、12、13為葉節點。
* 父節點（parent）／子節點（child）：有根樹中，兩個相鄰的節點，離根較近的節點是另一個節點的父節點，反之則為子節點。
範例圖中，節點3為節點9、10的父節點；節點9、10為節點3的子節點。
* 祖先（ancestor）／子孫（descendant）：有根樹中，一個節點的祖先包含了它的父節點和其父節點的祖先。反過來說，對於一個節點的祖先，這個節點為它的子孫。
範例圖中，節點2為節點5、6、7、8的祖先；節點5、6、7、8為節點2的子孫。
* 距離（distance）：兩點間的距離是它們之間的路徑的邊數或邊權總和。
範例圖中，節點7和節點12的距離為6。
* 深度（depth）：有根樹中，一個點的深度是它到根的距離。
範例圖中，節點7的深度為3。
* 高度（height）：有根樹中，一個點與它的子樹中距離最大的葉節點的距離稱為高度。根的高度稱為這整棵樹的高度。
範例圖中，節點1（根節點）的高度為4，節點3的高度為2。
* 子樹（subtree）：移除一個點後，原樹會被拆成很多棵樹，稱為子樹。有根樹中，一個節點的子樹通常泛指它的所有子孫，包含自己。
範例圖中，節點3、9、10、11、12、13為一棵子樹。
* 二元樹（binary tree）：每個節點都至多只有2個子節點的樹。
下圖為一棵二元樹。
### 3.3 二元樹
二元樹又比樹多了些性質。
#### 3.3.1 二元樹的遍歷
一棵二元樹的遍歷分為「前序（pre-order）」、「中序（in-order）」、「後序（post-order）」三種，三者的差別為造訪根節點的時機。
* 前序遍歷：遍歷根節點→遍歷左子樹→遍歷右子樹
* 中序遍歷：遍歷左子樹→遍歷根節點→遍歷柚子樹
* 後序遍歷：遍歷左子樹→遍歷右子樹→遍歷根節點
實作上我們以DFS的方式，再藉由改變遍歷根節點的時機仿造出三種不同遍歷的方式。
以下為範例程式：
```cpp=
int lc[], rc[];
// lc[i]表示節點i的左子節點，rc[i]表示節點i的右子節點，0表示不存在
void dfs(int x)
{
// cout << x << '\n'; （前序）
if (lc[x])
dfs(lc[x]);
// cout << x << '\n'; （中序）
if (rc[x])
dfs(rc[x]);
// cout << x << '\n'; （後序）
}
```
對於一棵二元樹，只要有其中序及前序或後序遍歷的順序即可還原出原本的二元樹長相。利用中序的「根節點位置的左右恰為左右子樹」的性質搭配分治法處理，複雜度為$O(n)$。
#### 3.3.2 二元搜尋樹（Binary Search Tree）
二元搜尋樹是二元樹的資料結構應用。其定義如下：
* 根節點的鍵值必大於左節點，必小於右節點
* 根節點的左右子樹都是一棵二元搜尋樹
對於任何一個序列，只要依照上面兩條規則就能蓋出對應的二元搜尋樹。而對於一個已排序的序列，其二元搜尋樹會是一條鏈，蓋樹的時間複雜度會退化至$O(n^2)$，深度變成$O(n)$。所以二元搜尋樹本身並不是很實用，真正實用的是其推廣結構。
### 3.4 樹直徑及樹圓心
* 樹直徑：一棵樹的直徑為樹中最遠的兩點間的簡單路徑。
* 樹圓心：一棵樹的圓心為能使樹高度最小的根。
要找出樹直徑，可以從任意一點$u$開始進行DFS，並從距離$u$最遠的點$v$再DFS一次，得到距離點$v$最遠的點$w$。則$u$到$w$的路徑即為樹直徑。
而樹圓心會是直徑上的某個節點，所以可以在第二次的DFS中一起算出。
### 3.5 樹重心
* 樹重心：一棵樹的重心為樹上的某個節點，使得以此節點為根時，所有子樹的大小皆不超過整個樹的一半。
要找出樹重心，可以先以任意一點為根，進行一次DFS後算出以各節點為根的子樹大小。
此時可以得知，當點$i$為根時，新的樹的最大子樹大小會是點$i$的所有子節點中子樹最大者以及節點總數減去子孫總數再減1的最大值。算出每個節點的值後，即可得到此樹的樹重心。
樹重心有以下性質：
* 把兩棵樹通過一條邊相連得到一棵新的樹，那麼新的樹的重心會在連接原來兩棵樹的重心的路徑上。
* 把一棵樹添加或刪除一個葉節點，那麼它的重心至多只移動一條邊的距離。
### 3.6 時間戳記
記錄一個有根樹遍歷時，設進入節點$i$的時間為$in_i$，離開的時間為$out_i$，可觀察到以下性質。
* $u$是$v$的祖先若且唯若$in_u \le in_v$且$out_v \le out_u$，反之亦然。
* 設一陣列$arr$，滿足$arr_{in_u} = u$，稱為樹壓平。樹壓平能將樹視為一個序列進行操作，在往後的算法會再詳細說明。
* 一個有根樹節點$u$的子樹正好會是樹壓平的區間$[in_u, out_u]$。
故時間戳記基本上可以先被認為是判斷祖先子代關係的工具。
### 3.7 最低共同祖先（lowest common ancestor）
簡稱LCA。在一棵有根樹上兩節點的最低共同祖先即為其祖先的交集中，深度最深的祖先。
暴力搜尋LCA的複雜度為$O(n)$，不甚理想。使用倍增法可以大幅提升尋找LCA的效率。
#### 3.7.1 倍增法（prefix doubling）
我們可以事先存好每個節點往上$2^k$層的祖先。
```cpp=
int ac[k][n]; // 表示節點n第2^k層的祖先
for (int i = 1; i <= k; i++)
for (int j = 1; j <= n; j++)
{
ac[i][j] = ac[i - 1][ac[i - 1][j]];
// 第2^i層的祖先是第2^(i-1)層的祖先的第2^(i-1)層的祖先
}
```
建表複雜度為$O(kn)$。因為層數不會超過$n$層，故$k \le log_2n$，複雜度可寫成$O(n\ log\ n)$。
可以知道若$u$點的第$i$層祖先是$v$的祖先，則$u$點的第$i+1$層祖先也是$v$的祖先。我們可以對這個性質進行二分搜。若查詢的左右界為$[1, 2^(k+1)]$，我們就能確定每次查詢的中間值都會在我們建好的表上了。
以下範例中```ancestor(a, b)```回傳```true```若點$a$為點$b$的祖先；反之回傳```false```。可以用時間戳記的方式預處理，並以$O(1)$時間查詢。
```cpp=
int LCA(int a, int b)
{
if (ancestor(a, b)) // 特判a原本就是b的祖先的情況
return a;
for (int i = k; i >= 0; i--)
if (!ancestor(ac[i][a], b))
{
a = ac[i][a];
// 提高下界，把a設為第2^i層的祖先
}
return ac[0][a];
}
```
### 3.8 習題
<!--待補-->
## 4. 最小生成樹（minimum spanning tree）
簡稱MST。無向圖中，一個樹的子圖其包含原圖的所有節點稱為一棵生成樹。生成樹有許多長相，包含DFS或BFS的路徑其實都可以構成一棵生成樹。在所有的生成樹中，邊權總和最小的生成樹即為最小生成樹。
### 4.1 並查集（disjoint set）
並查集是一種資料結構，它可以支援以下操作：
* 詢問某元素隸屬的集合。
* 合併兩個集合。
這裡的集合在圖論上通常會被當成「連通塊」，這也代表著並查集擁有查詢任兩點是否連通的功能。
並查集對於每個集合賦予一個「領導者」，每個元素只要找到領導者就可以知道所在的集合了。
實作上，由於一開始每個元素都尚未合併，都是自己一個集合，所以我們會令```group[i] = i```，表示集合的領導者是自己。合併時只要在兩個集合的領導者間連一條邊即可。
實作並查集時，通常需要兩個函數，功能分別為尋找某元素隸屬的集合的領導者及合併兩集合。
以下範例中，```group[i]```指的是元素```i```隸屬的集合的領導者，而```sz[i]```指的是元素```i```隸屬的集合的大小，此陣列的值只對目前集合的領導者有效。
```cpp=
void init(int n) // 初始化
{
for (int i = 0; i < n; i++)
group[i] = i, sz[i] = 1;
}
int fnd(int a) // 尋找隸屬集合的領導者
{
if (a == group[a])
return a;
return group[a] = fnd(group[a]); // 順便將領導者與元素間所有點的領導者值更新
}
void uni(int a, int b) // 合併兩集合
{
int x = fnd(a), y = fnd(b);
if (x == y) // 兩元素所在集合相同
return;
else
group[x] = y, sz[y] += sz[x]; // 將x領導的集合併入y領導的集合中
}
```
### 4.2 Krsukal's algorithm
我們將原圖中連接一部分點的生成樹稱為最小生成子樹，可以發現一些特性：
* 一個單獨的點，可以視作一棵最小生成子樹。
* 兩棵最小生成子樹連結成一棵最小生成子樹，以兩棵最小生成子樹之間權重最小的邊連接，顯然是最好的。
* 三棵最小生成子樹連接成一棵最小生成子樹，先連結其中兩棵權重最小的最小生成子樹，再連接第三棵，總是比較好。
所以可以用貪心法，從最小權重的邊開始選起。若目前權重最小的邊其兩個端點隸屬於不同的集合，則選取該條邊，也就是連接兩棵最小生成子樹；若兩個點隸屬同一集合，也就是兩點間已連通，則不選擇該條邊。
先對每條邊以邊權排序後，即可依上述的做法找出最小生成樹。複雜度$O(E(log\ E+\alpha (V))$，其中$\alpha(x)$為阿克曼函數的反函數，成長速率極慢，幾乎可視為常數。
另外，最小生成樹還有Prim's algorithm及Borůvka’s algorithm，兩者較不常見，在此先不說明。
### 4.3 次小生成樹
枚舉不在生成樹中的邊$(u, v)$，放入最小生成樹後再拔掉最小生成樹中$u$、$v$之間路徑的邊權最大的邊，取最小值，即為次小生成樹。理論上複雜度會是$O(EV)$，可以再優化。
觀察：擺一條新的邊$(u,v)$進去一棵樹，必定會在$u$、$v$之間形成一個環。所以只要拆掉除了$(u,v)$以外這個環上權重最大的邊，就能形成新的、對於這條邊次小的樹。而環上權重最大的邊即為$u$、$v$間路徑的最大值，故我們能用LCA來尋找這條邊。總複雜度為$O(E(log\ E+\alpha (V))$。
### 4.4 習題
<!--待補-->
## 5. 最短路徑
最短路徑即為兩點間所有路徑中邊權和最小者。最短路徑上不允許存在負環，否則可以經由不斷通過負環讓路徑權重和持續變小。
### 5.1 單點源最短路徑
即求出一個點到所有點的最短路徑。
#### 5.1.1 鬆弛（relaxation）
對於任意兩個點$u$、$v$，如果起點到它們的距離$d_u$、$d_v$滿足$d_u+w_{u, v}<d_v$，那我們就可以把$d_v$更新成$d_u+w_{u, v}$，使$s$到$v$的距離變短，這個動作就叫鬆弛。
#### 5.1.2 Bellman-Ford algorithm
把起點的最短路徑設為0，不斷枚舉所有邊，嘗試每條邊是否能進行鬆弛，直到所有邊都無法進行鬆弛為止。每次鬆弛複雜度為$O(E)$。
因為最短路徑不會通過相同的點兩次，所以在沒有負環的情況，至多只要鬆弛$V-1$次就可以得到最短路徑。至多總共要鬆弛$V$次，故總複雜度為$O(VE)$。
若在第$V$次時還有邊能進行鬆弛，表示此圖有負環。故Bellman-Ford也可當作是判斷負環的方法。
#### 5.1.3 Dijkstra's algorithm
如果邊權都是非負實數，會存在一個性質：用完成一部分的最短路徑樹上的點去鬆弛其他不在樹上的點，所得到的離根最近的點肯定也在最短路徑樹上。
我們可以利用此性質，先將起點的最短路徑設為0，每次選擇當前尚未放入最短路徑樹的點中路徑長度最小的，該點的最短路徑即確定。接著再對該點連出的每條邊進行鬆弛，直到所有點都在最小路徑樹為止。
最糟情況下每條邊都需被鬆弛一次，複雜度$O(E\ log\ E)$。
請注意，此作法僅限於邊權皆為非負實數使用。
### 5.2 多點源最短路徑
一口氣求出所有點對的最短路徑，亦可使用$V$次單點源最短路徑來完成這件事。
#### 5.2.1 Floyd-Warshall algorithm
Floyd-Warshall使用動態規劃計算多點源最短路徑。
令$dp[k][i][j]$代表只以點1到點$k$為中繼點的情況下$i$到$j$的最短路徑長。時間複雜度為$O(V^3)$，空間複雜度可藉由滾動陣列壓縮到$O(V^2)$。其實作容易，常數也很小。
若執行完畢後出現$dp[k][i][i] = 0$的情況，表示存在負環。故Floyd-Warshall也是一個判斷負環的方法。
### 5.3 習題
<!--待補-->
---
## 參考來源
* [2019板中校內資訊培訓講義](https://tg.pe/xUVD)
* 2019清大程式解題訓練營講義
* [Competitive Programmer's Handbook](https://tg.pe/x9tw)
此份講義中所有圖皆使用[Draw Graph](https://tg.pe/xhby)製作
---
###### tags: `2019師大附中資訊校隊培訓`
###### Last Updated: joylintp 2019/10/30
Sign in with Wallet
Connect another wallet