Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

2020 Week 5: Graph Structures

本週要繼續介紹些基本的資料結構
並且接下來將使用這些資料結構構造(解釋)一些演算法

底下的術語挺多的，各位不需馬上就得記起來，等到未來碰到再回來多複習幾遍

Graph

圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

圖的術語：

點 (vertex)：組成圖的最基本的元素
邊 (edge)：點與點的關係
$u$ 的鄰點 (neighbors)：
$u$ 透過一個邊連到的所有點
有向圖 (directed graph)：邊帶有方向性
無向圖 (undirected graph)：每條邊都是雙向的
道路 (walk^[1])：點邊相間的序列， e.g.
$v_{0} e_{1} v_{1} e_{2} v_{2} . . e_{n} v_{n}$
行跡 (trail)： 邊不重複的道路
路徑 (path)： 點不重複的道路^[2]
環 (cycle)：路徑的起點與終點連接後形成環
度 (degree)：與該點連接的邊數量 (無向性)
入度 (in-degree)：連到該點的邊數量 (方向性)
出度 (out-degree)：該點往外連的邊數量 (方向性)
走訪/遍歷 (traversal/search)：走完全部的點或邊

口語上常會把路徑表示成道路，但根據多數的圖論書籍，這兩者定義是不同的

在討論圖的邊，常會有

u

是邊起點與

v

是邊終點的慣例用符

上面這就是一種有向圖

圖的儲存

通常圖用鄰接表 (adjacency list) 或鄰接矩陣 (adjacency matrix) 儲存資料

鄰接表

struct edge { int u, v, w; }; // 兩個相鄰點與邊權重
vector<edge> E;

int main() {
    :
    .
  while (M--) {
    scanf("%d%d%d", &u, &v, &w);
    E.push_back({u, v, w});
  }
}

直接紀錄所有邊(兩點與權重)

或是

struct vertex { int v, w; }; // 鄰點與邊權重
vector<vertex> E[MAXN];

int main() {
    :
    .
  while (M--) {
    scanf("%d%d%d", &u, &v, &w);
    E[u].push_back({v, w});
  }
}

為每個點紀錄其所有鄰點與之間的權重

鄰接矩陣

int E[MAXN][MAXN];

int main() {
    :
    .
  while (M--) {
    scanf("%d%d%d", &u, &v, &w);
    E[u][v] = w;
  }
}

為每對點紀錄邊的關係 (有無權重可代表是否有邊)

使用鄰接矩陣要注意空間成本

Tree

樹 (Tree)，這個資料結構在圖像化看起來像顆倒掛的樹，根在上，而葉子在下。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

樹的術語及特點：

樹是種有向無環連通圖
節點 (node)：樹上的點不使用圖的術語：點 (vertex)
父 (parent)：節點能反向拜訪的第一個節點
子 (child)：節點能正向拜訪的第一個節點
祖先 (ancestor)：節點能反向拜訪的所有節點
孫子 (descendant)：節點能正向拜訪的所有節點
根 (root)：沒有父節點的節點
葉 (leaf)：沒有子節點的節點
深度 (depth)：節點的深度為從根到該節點所經過的邊數
森林 (forest)：一個集合包含所有不相交的樹
每個非根節點只有一個父節點

在數學上的圖論領域，通常樹是種無向無環的連通圖

樹的儲存

將節點本身的資料，以及連接的其他節點位置以 node 結構保存下來

struct node {
  int val; // value
  node *ch1, *ch2, *ch3, *ch4;
  // vector<node*> ch;
}

這是每個節點至多有四個孩子的樹

Union-Find Forest (併查森林)

考慮設計一個結構，
它要能存放一些集合，且這些集合之間沒有相同元素
這樣的集合族稱作 Disjoint sets

Disjoint sets 通常應用在"分類"問題中

直觀的想法是將每個集合有哪些元素，用陣列或連結串列紀錄起來
而常見的集合操作有，新增、刪除、(取)聯集、取交集(?)、取集合大小

可以思考一下這些操作的複雜度要多少

但併查森林則是將紀錄方式從 "集合有哪些元素" 改為 "元素屬於哪個集合"

Initialization

for (int v = 1; v <= N; v++) group[v] = v;

Find

Find 會尋找某個元素屬於哪個集合

int Find(int v) {
  if (v == group[v]) return v;
  return Find(group[v]);
}

假設有元素

1

5

，其中

1, 2

一組，

3, 4, 5

一組。

下 Find(5) 指令，會回傳

3

Path Compression

稍微想像一下可發現，若樹長這樣：

那麼明顯 Find(i) 的複雜度為

O (N)

直覺的，如果樹不是長得這麼長，而是一個個節點都直接接在

3

底下
那麼 Find(i) 的複雜度似乎就能下降了。
所以每當回溯時就順便把最上層 group 的標號^[3](也就是

3

) 給所有拜訪完的節點

i

也就是改寫為：

int Find(int v) {
  if (v == group[v]) return v;
  return group[v] = Find(group[v]); // Path Compression
}

於是原本的森林下 Find(5) 指令

森林會變成：

Union

Union 會將兩個集合合併起來

再次提醒：此集合族是 disjoint 的

void Union(int u, int v)
  { group[Find(u)] = Find(v); }

若對下圖這樣的情況，做 Union(4, 2); 也就是將

4

的 root

3

合併到

2

的 root

1

則上圖會變為下圖這樣：

有種方式稱作 Union by rank/size，將 rank/size 小的樹併到 rank/size 大的樹下，可加快許多。

範例 UVa OJ 879 Circuit Net：

cin.ignore(); // for getline
while (getline(cin, pins)) {
  if (pins.empty()) break; // for getline

  stringstream sin(pins);
  while (sin >> a >> b) Union(a, b);
}

int cnt = 0;
for (int i = 1; i <= N; i++) if (group[i] == i) cnt++;

std::stringstream 是很方便的東西，不過據說效率不夠優。

練習：

UVa OJ 10583 Ubiquitous Religions
UVa OJ 11987 Almost Union-Find
TIOJ 1192 鑰匙設計
 CODEFORCES 1253D Harmonious Graph

搜尋

有了圖，有了樹，可以開始討論這回事了

狀態：搜尋所能觸及到的可能性/目標
狀態轉移：每當狀態改變後，前個狀態到下個狀態的過程
狀態空間：若把狀態看作點，而狀態轉移看作邊，狀態空間為包含這些點與邊的圖

回憶一下上面曾介紹的術語：

走訪/遍歷 (traversal/search)：走完全部的點或邊

遍歷也是種搜尋，但"走完"可能得付出龐大的時間成本，或是空間成本
根據狀態空間規模，須用一些手段使得能更快速的找到所想要的東西。

本章使用的圖論符號慣例：

$V$ (Vertex) 表節點集合，表達單一點常用
$u$ ,
$v$
$E$ (Edge) 表邊集合，通常起點用
$u$ 、終點用
$v$ 作為點符號

$u \to v$ 邊可寫成
$(u, v) \in E$ 或是
$u v \in E$

深度優先搜尋 (Depth-first Search)

顧名思義，要盡量以深層的方式搜尋，以下簡稱 DFS

走訪方式：每拜訪一點就往其一鄰點拜訪下去。

這裡的走訪為走遍所有點 (而非邊)
若中途碰到曾走過的點不往下繼續走。^[4]

按照上圖，走訪順序為

1

依照自然數列開始走訪到

15

。

DFS 走過的道路為樹，稱此樹為 DFS 樹：

(圖上節點左上角的數字代表深度)

void dfs(int u, int dep) { // dep := depth
  for (int v: E[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    dfs(v, dep+1);
  }
}

這裡 for 迴圈採用 Range-based 寫法

其中 vis[i]^[5] 為 true 代表此點已拜訪完，下次遇到此點直接略過。
所以在開始進行走訪前，將起點設為拜訪完：

vis[root] = true; // root 代表走訪此圖的起點
dfs(root, 0);

DFS 除了能夠以上述遞迴方式呈現，也可以採用 stack 來實作：

stack<tuple<int, int, int>> dfs;
dfs.emplace(root, 0, 0);
vis[root] = true;

while (!dfs.empty()) {
  auto [u, cur, dep] = dfs.top(); dfs.pop(); // cur := current index

  for (int i = cur; i < E[u].size(); i++) {
    int v = E[u][i];
    if (vis[v]) continue;

    vis[v] = true;
    dfs.emplace(u, i, dep); // 往下個深度前先保存當前狀態
    dfs.emplace(v, 0, dep+1);
    break;
  }
}

雖然實務上是以遞迴方式實作為主流，但還是建議讀懂這份程式碼

練習：

LeetCode 102 Binary Tree Level Order Traversal
LeetCode 236 Lowest Common Ancestor of a Binary Tree

狀態空間搜尋^[6]

搜尋某個狀態，可以利用函式與參數表示
例如會把 f(1, 2, 3) 和 f(3, 4, 5) 這樣的函式呼叫，當作不同的狀態去接觸(求解)它。

範例 UVa OJ 572 Oil Deposits：

題目要求一個區域中有幾個連通圖
所謂的連通，就是圖中任意兩點間至少有一條路徑

當接觸到 dfs(r, c) 狀態時，代表這裡有包含座標

(r, c)

的 oil deposit (前提 plot[r][c] 為 '@')
而 DFS 走訪時，只需確保不再重複走到走過的點，所以走過就設 '*'

void dfs(int r, int c) {
  if (plot[r][c] == '*') return;
  plot[r][c] = '*';

  for (int dr = -1; dr <= 1; dr++)
    for (int dc = -1; dc <= 1; dc++) //雙重迴圈讓八個方位都走
      if (r+dr >= 0 && r+dr < m && c+dc >= 0 && c+dc < n)
        dfs(r+dr, c+dc);
}

只要是連通圖，DFS 都能把此圖走訪完
這裡簡單算走進幾次連通圖就好

int count = 0;
for (int i = 0; i < m; i++)
  for (int j = 0; j < n; j++)
    if (plot[i][j] == '@') { dfs(i, j); count++; }

練習：

LeetCode 113 Path Sum II
* LeetCode 437 Path Sum III

廣度優先搜尋 (Breadth-first Search)

顧名思義，要盡量以寬廣的方式搜尋，以下簡稱 BFS

走訪方式：每拜訪一節點就將其全部鄰點拜訪過。

同 DFS，碰到曾走過的點則不往下繼續走

按照上圖，走訪順序為

1

依照自然數列開始走訪到

15

。

對於一個點，會經歷以下階段：

未拜訪：不曾進入隊列
拜訪中：進入隊列
拜訪完：離開隊列

則 BFS 的流程為：

將起點(root)加入隊列中
每次將一個拜訪中的點
$u$ 的所有未拜訪鄰點加進隊列，而
$u$ 就此拜訪完畢
重複動作 2. 直至隊列為空

若圖是連通圖，則 BFS 會將所有點都拜訪過

queue<int> Q;
Q.push(root); //root 代表走訪此圖的起點
vis[root] = true;

while (!Q.empty()) {
  int u = Q.front(); Q.pop();
  
  for (auto& v: E[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    Q.push(v);
  }
}

根據條件應將不合法的走法濾掉，在 Q.push() 之前可判斷一下。
BFS 跟 DFS 結構只差在 stack 和 queue，除此之外兩者是非常相似的

與 DFS 同樣，由於不會走訪曾走過的點，所以 BFS 走完後也會有個 BFS 樹：

最短步數

搜索地圖起點到任意點的最短步數/路徑，
例如地圖上 * 代表牆(不能走)，$ 代表路，% 是起點，@是終點
且每一步只走上下左右一格：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  $  %  $  $  *  *  
*  $  $  $  $  *  *  $  *  *  
*  $  *  $  *  *  *  $  *  *  
*  $  *  $  $  $  *  $  *  *  
*  $  *  $  *  $  $  $  *  *  
*  $  $  *  *  $  *  $  $  *  
*  *  $  $  $  *  *  *  $  *  
*  @  *  *  $  *  $  $  $  *  
*  $  *  *  $  *  $  *  $  *  
*  $  $  $  $  $  $  *  *  *  
*  *  *  *  *  *  *  *  *  *

BFS 可以應用在這^[7]：

*  *  *  *  *  *  *  *  *  *  
*  *  *  *  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 13 *  *  *  9  *  
*  21 *  *  14 *  12 11 10 *  
*  20 *  *  15 *  13 *  11 *  
*  19 18 17 16 15 14 *  *  *  
*  *  *  *  *  *  *  *  *  *

其中上面數字代表深度。
這個走法就跟粘菌走迷宮同樣

範例 UVa OJ 11624 Fire!：

最開始先將 Joe 與各火點放進 queue 中，以便讓 BFS 以此為起點走訪：

for (int r = 0; r < R; r++) {
  scanf("%s", input);
  for (int c = 0; c < C; c++) {
    if (input[c] == '#') maze[r][c] = 0;
    if (input[c] == '.') maze[r][c] = INF;
    if (input[c] == 'J') J.push({r, c, 0}), maze[r][c] = INF, vis[r][c] = true;
    if (input[c] == 'F') F.push({r, c, 0}), maze[r][c] = 0;
  }
}

(其中 INF^[5:1] 為一個非常大的數字，例如 int 的上限)

Joe 不能被火燒到，所以 Joe 一定要走得比火快
由此，算出各點何時火會燒過來就能判斷 Joe 是否能比火先到

搜尋火到各點的最短路：

while (!F.empty()) {
  point f = F.front(); F.pop();

  for (int d = 0; d < 4; d++) {
    int nr = f.r+dr[d], nc = f.c+dc[d];
    if (nr == R || nc == C || nr < 0 || nc < 0 || maze[nr][nc] != INF || maze[nr][nc] == 0) continue;
    
    maze[nr][nc] = f.t + 1;
    F.push({nr, nc, f.t+1});
  }
}

其中 point 結構三個變數為 row, column 與 time (火抵達的時間)
並利用 dr 與 dc 以當前所在點走遍四個方向：

              /* 左, 右, 下, 上 */
int const dr[] = {0, 0, -1, 1};
int const dc[] = {-1, 1, 0, 0};

現在 maze (也就是地圖) 上有紀錄火到的時間了。
接下來讓 Joe 去尋找最短路：

int escape = -1;
while (!J.empty()) {
  point j = J.front(); J.pop();
  if ((j.r == R-1 || j.c == C-1) || (j.r == 0 || j.c == 0)) {
    escape = j.t + 1;
    break;
  }

  for (int d = 0; d < 4; d++) {
    int nr = j.r+dr[d], nc = j.c+dc[d];
    if (vis[nr][nc] || j.t + 1 >= maze[nr][nc]) continue;
    
    vis[nr][nc] = true;
    J.push({nr, nc, j.t+1});
  }
}

j.t + 1 >= maze[nr][nc] 就能看 Joe 走這點是不是會被火燒
最後判斷走到邊界，就成功逃脫了！

練習：

UVa OJ 532 Dungeon Master
LeetCode 542 01 Matrix
LeetCode 994 Rotting Oranges
STEP5 0127 攻略妹妹
 LeetCode 127 Word Ladder
UVa OJ 11234 Expressions
UVa OJ 1599 Ideal Path
* CODEFORCES 1307D Cow and Fields

Backtracking

利用各種可得的限制來做搜尋目標中的偷吃步

八皇后問題^[8]：西洋棋盤上任意擺放八個皇后彼此都不互攻的情況有幾種？

如下圖是其中一種合法的擺法
^[8:1]

若想著把每一種任意擺放可能性列出來，再來挑選可行的盤面，
將有

(\binom{64}{8}) = 4426165368

^[9] 種盤面要產，明顯的程式會跑很久

而兩個皇后放在同個 row 或 column 上一定會互攻，所以只需在每個 row 或 column 擺放一個皇后就好：

int dfs(int row) {
  if (row == 8) return 1;
  
  int sum = 0;
  for (int col = 0; col < 8; col++)
    if (check(row, col)) {
      board[row] = col; // 在 (row, col) 放置一個皇后
      sum += dfs(row + 1);
    }
  
  return sum;
}

這邊的 check(r, c) 就是本節的主題了，
在轉移狀態(盤面)前，若能預感(?)這狀態不是想要的，就中斷轉移，然後 backtrack 到原狀態，繼續進行別的狀態轉移

用 check(r, c) 檢查將皇后放置在

(r, c)

後是否能繼續再放置其他皇后。

用點幾何概念的話，會發現 check() 只需要

O (N = 8)

就能做到：

bool check(r2, c2) {
  for (int r1 = 0; r1 < r2; r1++) {
    int c1 = board[r1];
    if (c1 == c2 || c1-c2 == r1-r2 || c1-c2 == r2-r1) return false;
  }
  
  return true;
}

枚舉的盤面會少於

N!

很多，因為 check() 剪掉了許多不必再繼續遞迴下去的 DFS 樹枝。

^[10]

練習：

UVa OJ 524 Prime Ring Problem
UVa OJ 211 The Domino Effect

看英文 walk 這字，帶有一種隨意的感覺，是種無限制的路 ↩︎
很多人無法很好的區分道路與路徑，甚至行跡，通常得仔細讀上下文 ↩︎
這邊容易誤會，因為 disjoint sets tree 的"根"，是我們進行遞迴下探走到的"葉"。 ↩︎
注意，這裡的圖剛好是連通的。 ↩︎
這個變數將成為以後的慣例 ↩︎ ↩︎
State space search ↩︎
有時間可以玩玩看 pipes，裡頭有附上 source code ↩︎
Wikipedia/ Eight queens puzzle ↩︎ ↩︎
就是組合
$C$
$64$ 取
$8$ 的意思 ↩︎
Mathworks/ The Eight Queens Problem ↩︎

2020 Week 5: Graph Structures

Graph

圖的儲存

鄰接表

鄰接矩陣

Tree

樹的儲存

Union-Find Forest (併查森林)

Initialization

Find

Path Compression

Union

範例 UVa OJ 879 Circuit Net：

練習：

搜尋

深度優先搜尋 (Depth-first Search)

練習：

狀態空間搜尋[6]

範例 UVa OJ 572 Oil Deposits：

練習：

廣度優先搜尋 (Breadth-first Search)

最短步數

範例 UVa OJ 11624 Fire!：

練習：

Backtracking

練習：

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory

狀態空間搜尋^[6]