2020 競技程設教材 HackMD Book

2020 Week 11: Graph

本主題會用到第五週及第七週教材的內容

不熟的話，底下介紹的都看不懂了

圖論最為重要觀念就是 "連通"，
若說此圖為連通圖，則所有點能透過邊接到任一點 (弱連通)^[1]。
而不只接上還能走過去(有向邊)^[2]，則為強連通。

例如：

上圖弱連通但非強連通。

若是這樣：

則上圖為強連通。

點與邊的表示方式

以下兩個結構體，將成為本篇的慣例

• 點

struct node {
  int id, w; // id := 點編號, w := 連結到此點的權重 (邊權重)
  bool operator<(const node &rhs) const {
    return w > rhs.w; // 使 priority_queue 為 min heap
  }
};

• 邊

struct edge {
  int u, v, w; // u := 起端編號, v := 終端編號, w := 權重
  bool operator<(const edge &rhs) const {
    return w > rhs.w; // 使 priority_queue 為 min heap
  }
};

討論圖的邊，常會有

$u$ 是邊起點與

$v$ 是邊終點的慣例用符

Minimum spanning tree (MST)

最小生成樹 (Minimum spanning tree) 簡稱 MST。

給定圖

$G=(E,V)$，使用

$E$ 子集連結所有點 (來自

$V$) 所得到的樹為生成樹。

$E$ 為邊集合，

$V$ 為點集合

若帶權重圖的某生成樹為所有生成樹中權重總和最小，則稱此為最小生成樹

^[3]

給定一個連通圖，找出一個最小生成樹

Kruskal 演算法

Kruskal 用了兩個重要的觀念：

• 樹是無環的連通圖
• 若圖中只有點沒有任何邊，那麼每個點都是一個獨立的連通塊。

這有什麼可利用的呢？

若將一點連向另一點，整張圖就少了一個連通塊，
反覆操作，圖最終只剩一個連通塊，若最終連通塊沒有環，那他就是樹，且為此圖的生成樹。

於是在連通塊與連通塊相連這個動作，確保產生的連通塊無環就行：
連通塊

$A$ 想與連通塊

$B$ 相連，只要

$A\ne B$，那麼相連的新連通塊保證無環。

怎樣產生出最小生成樹？

所以若在

$A$ 與

$B$ 相連時每次考慮最小權重的邊，那最終產生的一定是最小權重的生成樹

沒錯哦，這是最優子結構

^[4]

實作上先將每個邊依照權重排序，

vector<edge> E;
  :
  .
sort(E.begin(), E.end(), [&](edge x, edge y) { return x.w < y.w; });

接著用 DFS 判斷塊與塊是否為同個連通塊，若不是的話就能相連起來。
DFS 每次都將連通塊的邊遍歷，複雜度為

$O(|E{|}^2)$

還記得 Union-Find Forest 嗎？分類問題包括連通塊的分類也能使用它：

for (edge e: E) {
  int a = Find(e.u), b = Find(e.v);
  if (a != b) {
    Union(e.u, e.v);
    cost += e.w;
    MST.push_back({u, v, w});
  }
}

複雜度約為

$O(|E|\log |E|+|E|\cdot \alpha )$
其中

$\alpha =\alpha (|E|)$ 為 Union-Find Forest 的時間成本 (通常很小)

範例 UVa OJ 10369 Arctic Network：

很直覺的，使 outpost 都能通訊的簡單方法，就是做出樹
畢竟若兩點已能通訊，加入一條形成環的邊不會更好。

而想使 D 下降的方法就是將 network 上的 distance 盡量小，也就是要求最小生成樹
而生成樹上較大的邊就用 satellite channel 來解決

先把 outpost 之間的距離算出來：

vector<edge> E;
for (int v = 0; v < P; v++) {
  scanf("%lf%lf", &C[v].x, &C[v].y);
  for (int u = 0; u < v; u++) E.push_back({u, v, dist(C[u], C[v])});
}

接著將最小生成樹 (network) 上最大的距離找出來：

sort(E.begin(), E.end(), [&](edge A, edge B) { return A.dist < B.dist; });

vector<double> D;
for (edge e: E) {
  int a = Find(e.u), b = Find(e.v);
  if (a != b) {
    D.push_back(e.dist);
    Union(e.u, e.v);
  }
}

printf("%.2lf\n", D[P-S-1]);

練習：

TIOJ 1211 圖論 之 最小生成樹
AIZU 1280 Slim Span
NCPC 2018 Final Problem E Connecting Cities
TIOJ 1445 機器人組裝大賽
TIOJ 1795 咕嚕咕嚕呱啦呱啦

---

Prim 演算法

Prim 維護一個未完成的生成樹
其精神是：每次將樹周遭有最小權重的邊接到樹上，使樹最終成長至最小生成樹

傑出的一手貪心策略

^[5]

Prim 用了兩個重要的觀念：

• 樹是無環的連通圖
• 若圖中只有點沒有任何邊，那麼每個點都是一個獨立的連通塊。

跟 Kruskal 一樣呢

首先隨便找任意點，作為那個初始的"未完成的生成樹"，也就是一塊無環的連通圖

$A$
每次將

$A$ 能觸及到的最小權重的邊接上

$A$，那最終產生的一定是最小權重的生成樹

跟 Kruskal 不同的是，這裡枚舉的是"點"

vector<node> E[maxn]; // maxn 為最大節點數
  :
  .
priority_queue<edge> Q; // 每次挑最小權重的邊
Q.push({1, 1, 0}); // 初始的生成樹 (只有一個點)

while (!Q.empty()) {
  edge e = Q.top(); Q.pop();
  int u = e.v;

  if (vis[u]) continue; // 避免出現環
  vis[u] = true;
  
  cost += e.w;
  MST.push_back(e);
  for (node v: E[u]) if (!vis[v.id]) Q.push({u, v.id, v.w});
}

複雜度約

$O(|E|{\log }_2|E|)$

練習：

UVa OJ 908 Re-connecting Computer Sites
ACM-ICPC 2005 Southwestern 3505 Buy or Build

A* 搜尋法則

是路徑搜尋演算法的一個抽象觀點

A* 在節點

$n$ 有個評估函數

$f(n)=g(n)+h(n)$
當

$f(n)$ 大於門檻時就剪枝

$g(n)$ 表示從起點到節點

$n$ 的成本

$h(n)$ 表示從節點

$n$ 到終點的成本

評估函數是根據欲求解問題而設計，討論上是相當自由的

例如：

• 當
  $g(n)$ 是搜尋深度(或最短路步數)， 即 Breadth-first Search 是 A* 的特例
• 有種搜尋法叫做 Best-first Search，
  $h(n)$ 為該節點
  $n$ 到終點的歐幾里得距離

Iterative Deepening A* (IDA*)

IDA* 是種 A* 的變形，會逐步地將門檻變寬

假設門檻是遞迴深度 (maxd)，那麼就逐漸放寬標準：

for (int maxd = 0;; maxd++) if (dfs(0, maxd)) break; // 搜到就結束(break)

進行搜尋時一旦超過門檻就結束搜尋：

bool dfs(int d, int maxd) {
  if (d >= maxd) return false;
    :
    .
}

範例 AIZU 1271 Power Calculus：

直覺的，將所有羃次 (p) 的組合全部都試試看，找出最小的操作數 (operations) 就行：

int ans = n; // 操作數至多為 n

void dfs(int d) {
  if (p[d] == n) ans = min(ans, d);
  if (d == n-1) return;

  for (int i = 0; i <= d; i++) {
    p[d+1] = p[d] + p[i];
    dfs(d+1);
    p[d+1] = p[d] - p[i];
    dfs(d+1);
  }
}

執行前先設定邊界(當還未進行操作)：

p[0] = 1;

複雜度為

$O(n^n)$

複雜度頗高，

$n=10$ 的時候就能感受到輸出遲緩了

解答也許在深度還很小的時候就已經能找到了，所以將深度給定一個上限 (ops)：

bool dfs(int d) { // d := depth
  if (p[d] == n) return true;
  if (d == ops) return false;

  for (int i = 0; i <= d; i++) {
    p[d+1] = p[d] + p[i];
    if (dfs(d+1)) return true;
    p[d+1] = p[d] - p[i];
    if (dfs(d+1)) return true;
  }

  return false;
}

接著每次將深度/操作數 (ops) 的上限逐步提高：

while (scanf("%d", &n) && n) {
  for (ops = log2(n);; ops++) if (dfs(0)) break;
  printf("%d\n", ops); // 印出題目要求答案
}

但這題還不只如此，除了 IDA* 門檻設定以外，還得額外剪枝
當剩餘的操作數絕不可能湊出目標羃次 (n) 時，就不繼續以此狀態深入搜尋：

int mx = 0;
for (int i = 0; i <= d; i++) mx = max(mx, p[i]);
if ((mx << (ops-d)) < n) return false;

練習：

UVa OJ 11212 Editing a Book
UVa OJ 12558 Egyptian Fractions (HARD version)
UVa OJ 1343 The Rotation Game
UVa OJ 11846 Finding Seats Again
* UVa OJ 11376 Tilt!

Single-Source Shortest Paths

單源最短路徑 (Single-Source Shortest Paths) 簡稱 SSSP。
源點 (Source)，就是起點，通常問題都只是簡單求每條路徑的最小成本。

求單源點到其他所有節點的最短路徑總權重

Relaxation

想像自己在圖中是某一點 v，你看到你的鄰點們 u，他們告訴你：源點走到他們那裡的最小花費成本 cost[u] 是多少，同時你也知道那些點們要過來你這分別要花費多少成本 w (i.e. 邊權重)
考慮源點到自己這的最小成本 cost[v] 得知：

int update = cost[u] + w;
if (update < cost[v]) cost[v] = update;

Bellman-Ford's Algorithm

狀態

$S(n)$ 代表從源點到

$n$ 的最小成本
對於點

$v$ 顯然若

$(u,v)\in E$，則

$S(v)\le S(u)+\text{weight}(u,v)$
所以狀態轉移方程為

$S(v)=\underset{(u,v)\in E}{min}(S(u)+\text{weight}(u,v))$

這就是 relaxation

邊界(源點到源點最小成本)為

$S(\text{source})=0$
初始其餘的狀態設為無限大^[6]，以表示尚未得到最佳解

若是一次將所有邊都做 relaxation，那麼重複做，每次至少可以將一個點解出

在下方 Dijkstra's algorithm 有給出間接證明

最開始先從邊界(起點)的鄰點解出(relaxation)，接著是鄰點們的鄰點.. 直至所有的點。
所以至多只要重複做

$|V|-1$ 次，就能將所有點解出

$-1$ 是因為起點已經先被解出了

但假設

$(u,v)\in E.S(u)$ 是最優解，而

$S(v)$ 被

$S(u)$ 更新了，

$S(v)$ 還不一定是最優解

vector<edge> E;
  :
  .
memset(s, 0x3f, sizeof(s)); // 源點到任意點的成本初始為無限大
s[source] = 0;

for (int i = 1; i < V.size(); i++) // 共 V.size() - 1 次
  for (edge e: E)
    s[e.v] = min(s[e.v], s[e.u] + e.w);

找單源最短路徑就是這麼簡單

與第七週教材比較，兩者不同在於狀態求解的順序

Bellman-Ford 演算法可以簡單處理權重是負的情況：

• 對每邊做至多
  $|V|-1$ 次 relaxation 後，
• 要是某邊還能 relax，就表示有個負權重的邊能使路徑成本一直降低。

範例 UVa OJ 558 Wormholes：

先做

$|V|-1$ 次的每邊 relaxation

fill(s, s+n, INF);
s[0] = 0; // source
 
for (int i = 0; i < n-1; i++)
  for (int j = 0; j < m; j++)
    s[y[j]] = min(s[y[j]], s[x[j]] + t[j]); // relaxtion

接著就能判斷是否能回到過去

for (int j = 0; j < m; j++)
  if (s[x[j]] + t[j] < s[y[j]]) return true; // 還能做 relaxation

return false;

練習：

POJ 2387 Til the Cows Come Home
UVa OJ 10000 Longest Paths

Shortest Path Fast Algorithm (SPFA)

Bellman-Ford’s algorithm 的進化版本，
其動機是： 若邊被 relax 過，則它的鄰點可以直接進行 relaxation

memset(s, 0x3f, sizeof(s));
s[source] = 0;
memset(in_que, false, sizeof in_que); // in_que := is it in queue?

queue<int> Q;
Q.push(source);
in_que[source] = true;

while (!Q.empty()) {
  int u = Q.front(); Q.pop();
  in_que[u] = false;
  
  for (node v: E[u])
    if (s[v.id] > s[u] + v.w) {
      s[v.id] = s[u] + v.w; // relaxation
      if (!in_que[v.id]) Q.push(v.id), in_que[v.id] = true; // 下次直接讓 v.id 的鄰點做 relaxation
    }
}

長得很像 Dijkstra’s algorithm

最壞複雜度

$O(|V|\cdot |E|)$

平均而言

$O(k\cdot |E|)$， SPFA 提出者認為

$k$ 很小^[7]

練習：

UVa OJ 658 It’s not a Bug, it’s a Feature!

Dijkstra's Algorithm

Dijkstra 演算法可看作是 BFS 的帶權重版本

BFS (Breadth-first Search) 的詳細流程請複習第五週教材

再次從 Bellman-Ford 演算法出發，
但每次欲更新

$S(v)$ 需從已解的

$S(u)$ 做 relaxation，其中

$(u,v)\in E$

考慮 Bellman-Ford 演算法不斷更新

$S(v)$ 直至得最優解
每一次對所有邊都嘗試 relaxation 會有一些點被更新，姑且稱剛被更新的點為候選點
候選點都由已解的點 relax 過了，接下來只剩他們可以互相 relax 彼此
但值最小的點不會再被 relax 了

不被 relax 的條件是

$\mathrm{\forall }(u,v)\in E.S(u)+\text{weight}(u,v)>S(v)$，這裡

$u,v$ 是候選點
是因

$S(u)>S(v)>0$ 且

$\text{weight}(u,v)$ 不為負。此刻

$S(v)$ 就是最優解

籠統地說，是找不到點能靠加正值去更新比自己小的點

^[8]

vector<node> E[maxn]; // 邊集合
  :
  .

memset(s, 0x3f, sizeof(s)); // 源點到任意點的成本初始為無限大
vector<bool> vis(N, false); // 記錄點是否已得到解
priority_queue<node> Q; // 為從未解集挑出已解的狀態
Q.push({source, s[source] = 0});

接著找出源點到任意點的最短路徑，其就是 BFS 並搭配 Relaxation

而 queue 將保存候選點，且負責挑出最小的點 (已解狀態)

while (!Q.empty()) {
  node u = Q.top(); Q.pop();
  
  if (vis[u.id]) continue; // u 以前就找到解了
  vis[u.id] = true;
  
  for (node v: E[u.id]) { // v := 鄰點
    int update = s[u.id] + v.w; // 源點到 u 的最小成本 + u 到 v 的成本
    if (update < s[v.id])
      Q.push({v.id, s[v.id] = update /* relaxation */});
  }
}

其複雜度為

$O(|E|{\log }_2|V|)$

演算法的終止條件是 Q.empty() == true，
也就是說，若有個邊權重為負的，則 Q.push({v.id, update}); 將無盡的執行下去。

Bellman-Ford 演算法會提供解決之道

範例 POJ 3255 Roadblocks：

對於點 v 每次將比最短路 d1[v] 還大的更新值 ud 交給次短路 d2[v] 去做 relaxation

priority_queue<node> Q;
int d1[maxn], d2[maxn];

memset(d1, 0x3f, sizeof d1);
memset(d2, 0x3f, sizeof d2);
Q.push({1, d1[1] = 0});

while (!Q.empty()) {
  node u = Q.top(); Q.pop();

  for (node v: E[u.id]) {
    int ud = u.w + v.w; // ud := update

    if (ud < d1[v.id]) {
      Q.push({v.id, ud});
      swap(d1[v.id], ud); // 舊 d1[v.id] 要交給 d2[v.id] 做 relaxation
    }

    if (ud < d2[v.id] && ud > d1[v.id])
      Q.push({v.id, d2[v.id] = ud});
  }
}

練習：

NCKU OJ 10 探望麻衣
UVa OJ 10986 Sending email
UVa OJ 10801 Lift Hopping

All-Pairs Shortest Paths

全點對最短路徑 (All-Pairs Shortest Paths) 簡稱 APSP。
顧名思義，可以得知所有點與點之間的最短路徑，同樣的一般只需求最小花費成本而已。

Floyd-Warshall's Algorithm

設定狀態

$S(i,j,k)$ 為

$i$ 到

$j$ 只許以

$\{1,..,k\}$ 為中間點的最小總成本

而

$i$ 到

$j$ 間

$$S(i,j,k)=\{\begin{array}{ll}S(i,\underset{―}{k},k-1)+S(\underset{―}{k},j,k-1)& \text{若有經過點 }k\\ S(i,j,k-1)& \text{若不經過點 }k\end{array}$$

所以狀態轉移方程：

$$S(i,j,k)=min(S(i,j,k-1),S(i,k,k-1)+S(k,j,k-1))$$

邊界：

$$S(i,j,0)=\{\begin{array}{ll}0& \text{if }i=j\\ \text{weight}(i,j)& \text{if }(i,j)\in E\\ \mathrm{\infty }& \text{if }(i,j)\notin E\end{array}$$

經由滾動陣列優化方法，可使狀態三維降至二維：

同學自行研究，這很簡單的

int s[maxn][maxn];

for (int i = 1; i <= N; i++)
  for (int j = 1; j <= N; j++) s[i][j] = G[i][j]; // 邊界狀態

for (int k = 1; k <= N; k++)
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      s[i][j] = min(s[i][j], s[i][k] + s[k][j]);

範例 UVa OJ 125 Numbering Paths：

題目不是求最短路，而是求路徑數，但只需依樣畫葫蘆就行了！
若已知

$j\to i$ 有

$x$ 種路，

$i\to k$ 有

$y$ 種路，則根據乘法原理^[9]

$j\to k$ 至少有

$x\times y$ 種路：

for (int i = 0; i <= m; i++)
  for (int j = 0; j <= m; j++)
    for (int k = 0; k <= m; k++)
      M[j][k] += M[j][i] * M[i][k];

而根據題目，兩點之間的路徑中若有環，則兩點之間有無限多種路徑
若有環則表示某個點

$i$ 可透過一些路走回點

$i$；換句話說，存在點

$j$，其中

$i\to j$ 有一些路、

$j\to i$ 也有一些路，所以根據前面路徑數的求法，

$i\to i$ 就會有一些路產生：

for (int i = 0; i <= m; i++) {
  if (!M[i][i]) continue; // i 到 i 間沒有路
  for (int j = 0; j <= m; j++)
    for (int k = 0; k <= m; k++)
      if (M[j][i] && M[i][k]) M[j][k] = -1; // j 到 k 若經過點 i 就有無限多種路徑
}

練習：

TIOJ 1096 E.漢米頓的麻煩
Google Code Jam Kickstart Round F 2018 B Specializing Villages: Small dataset
UVa OJ 11838 Come and Go
UVa OJ 10724 Road Construction
Google Code Jam Round 1B 2017 C Pony Express

---

1. 把有向邊當成無向邊後，若連通的話就稱為弱連通 ↩︎

2. 只看兩鄰點

   $u$ 與
   $v$，
   $u\to v$ 表示這之間只有一條邊而
   $u$ 能走過去到
   $v$; 而
   $v$ 不能走到
   $u$ ↩︎

3. Wikipedia/ Minimum_spanning_tree.svg ↩︎

4. Wikipedia/ A demo for Kruskal's algorithm based on Euclidean distance. ↩︎

5. Wikipedia/ A demo for Prim's algorithm based on Euclidean distance. ↩︎

6. 也能設為其他具代表性的數字作為未知的總成本 ↩︎

7. 主編個人覺得 Dijkstra’s algorithm 實用期望值比較高 ↩︎

8. Wikipedia/ Dijkstra's algorithm runtime ↩︎

9. 建中數學科/ 第33單元排列組合 ↩︎