tags
成大高階競技程式設計 2020, ys

2020 Week 12: Graph

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

Articulation point (AP)

Articulation point 中譯關節點

當連通圖上此關節點被拔除，圖會分為多塊連通圖

通常只要求此連通圖為弱連通的

:::info 給定連通圖，找到所有 AP :::

考慮樹，顯然：

除葉以外，其餘的節點都為 AP
若根只有一個子節點，則不為 AP

graph {
  3 -- 4;
  3 -- 5 -- 6;
  5 -- 7;
  7 -- 8;
}

如何讓 AP 不再是 AP 呢？例如：將 $5$ 變非 AP，可讓 $7$ 連到 $3$，及 $6$ 連到 $4$。

digraph {
  {9 [ style=invis, width=0, label=""]}
  {3 -> 9 [ style=invis]}
  {3 -> 9 [ style=invis]}
  3 -> 4 [arrowhead=none];
  {"10" [ style=invis, width=0, label=""]}
  {3 -> 10 [ style=invis]}
  3 -> 5 -> 6 [arrowhead=none];
  6 -> 4 [color=red, arrowhead=none];
  { rank="same" 4->5 [ style=invis] }
  5 -> 7 [arrowhead=none];
  7 -> 3 [color=red, arrowhead=none];
  { rank="same" 6->7 [ style=invis] }
  7 -> 8 [arrowhead=none];
}

也就是說，若問連通圖中有哪些點是 AP，先遍歷出棵樹 (例如 DFS 樹) 接著直覺的，節點的子孫有邊回到比此節點還高¹ (淺)的節點，則此節點非 AP。

高指的是圖像的相對位置，淺指的是 depth 數字較小

而這個連向祖先的邊，稱作 back edge

Tarjan’s algorithm for APs

實作上透過下列兩個函數，以找出所有 AP

$\text{dep}(n)$ 代表節點 $n$ 的深度 (depth) 若節點還未拜訪過 $\text{dep}(n) = -1$
$\text{low}(n)$ 代表節點 $n$ 透過 back edge 能連向最高節點的深度值，若無 back edge 則為 $\text{dep}(n)$

low 這個詞應該是指深度較小的意思

²

Tarjan 用 DFS 遍歷出樹，所以從樹來看，當節點 $u$ 的的子節點 $v$ 有 $\text{low}(v) \ge \text{dep}(u)$ 就表示拔除 $u$ 會使 $v$ 走不到更高的節點，所以 $u$ 就是此圖的 AP

實作上：

當有 back edge 時表示能更新 low 值
用父與子節點總數 cnt 判斷該點是否為葉節點或不為 AP 的根節點

void dfs(int p, int u, int d) { // p := previous, d := depth
  dep[u] = low[u] = d;
  int cnt = !!d; // 待累計 u 的父與子節點總數
  bool back_error = false;

  for(int v: E[u]) if(v != p) { // v 是 u 的鄰點
    if(dep[v] != -1) {
      low[u] = min(low[u], dep[v]);
      continue;
    }
    
    cnt++;
    dfs(u, v, d+1);
    
    low[u] = min(low[u], low[v]);
    if(low[v] >= d) back_error = true; // v 沒有 back edge
  }

  if(cnt > 1 && back_error) AP.push_back(u);
}

根節點深度為 0

練習：

UVa OJ 315 Network ICPC World Finals 2003 Building Bridges CODEFORCES 194C Cutting Figure

Strongly Connected Components (SCC)

強連通是只屬於有向圖的概念

根據第十一週教材，

把圖的方向拿掉，連通的話稱此圖弱連通
加上方向後仍然連通，則此圖強連通

雖然有向圖不總有強連通性，但能把圖分成幾塊強連通子圖 而 SCC 要求的是分出盡量大的強連通子圖：

換句話說，就是子圖的點要盡量多如果不這麼找，會有很多種分法，至少單獨一點也算強連通子圖

³

:::info 給定圖，求圖有幾塊極大強連通子圖 :::

Kosaraju's Algorithm

連通意味著任兩點 $u, v$ 之間有路那麼把 $u\leadsto v$ 的各邊反過來，對 $v\leadsto u$ 也反過來，圖理當也連通

$u\leadsto v$ 表示 $u$ 到 $v$ 路徑

因為 $u\leadsto v$ 及 $v\leadsto u$ 兩路合併，能得到環，環反過來還是環 也就是說，對於強連通圖：

digraph {
  node[label=""]
  rankdir="LR"
  b -> c -> a
  a -> d [dir=back]
  c -> e -> d
  a -> b
}

把邊方向反過來仍具有強連通性：

digraph {
  node[label=""]
  edge[dir=back]
  rankdir="LR"
  b -> c -> a
  a -> d [dir=forward]
  c -> e -> d
  a -> b
}

對於無相圖，第五週教材提到 DFS 能判斷是否具有連通性
對於有向圖 DFS 拜訪到的節點與反邊圖 DFS 拜訪的節點相同，則為強連通

反邊圖就是把圖上的邊全改為反向

void forward(int u) { // 正向 DFS
  vis[u] = true;
  for (int v = 0; v < n; v++) if (E[u][v] && !vis[v]) forward(v); // 節點編號從 0 到 n-1
  st.push(u);
}

void backward(int u, vector<int>& sub) { // 反向 DFS
  vis[u] = true;
  for (int v = 0; v < n; v++) if (E[v][u] && !vis[v]) backward(v, sub);
  sub.push_back(u);
}

這裡 E 是鄰接矩陣，E[a][b] 表示有 a 到 b 的邊

stack st 紀錄有哪些點是在 forward 走過，但 backward 沒走過基於 stack 的特性，可將 forward 先一次做完，再一次次做 backward

memset(vis, false, sizeof(vis));
for (int u = 0; u < n; u++) if (!vis[u]) forward(u); 

memset(vis, false, sizeof(vis));
while (!st.empty()) {
  int u = st.top(); st.pop();
  
  if (!vis[u]) {
    vector<int> sub; // sub := subgraph
    backward(u, sub);
    SCC.push_back(sub);
  }
}

練習：

ICPC Regionals 2008 Taipei Road Networks UVa OJ 247 Calling Circles

Tarjan's algorithm for SCCs

與找圖中 articulation point 時類似，要利用到 DFS 樹的觀念但不能使用 $\text{dep}$ 函數，必須換成 $\text{dfn}$，定義為

$\text{dfn}(n)$ 代表節點 $n$ 的 DFS 走訪順序若節點還未拜訪過 $\text{dfn}(n) = 0$
$\text{low}(n)$ 代表節點 $n$ 透過 back edge 能連向最高節點的 dfn 值，若無 back edge 則為 $\text{dfn}(n)$

最高指的是 dfn 數字最小

⁴

連通圖是由環所構成的，且要找的是極大的連通子圖，所以當：

$\text{low}(n) < \text{dfn}(n)$ 表示有 back edge 能連通到更高的節點
$\text{low}(n) = \text{dfn}(n)$ 表示 $n$ 已經是極大連通子圖的最高節點

在實作上，會使用 stack st 記錄⁵目前搜索中的節點，對於連通兩點 $u, v$，從高處往低處搜索有 $u \leadsto v$，則透過 back edge 才會有 $v \leadsto u$；故搜索時欲建立 back edge 時，並不會考慮 st 中以外的節點

提醒，建立 back edge 就是在更新 low 值

void dfs(int u) {
  dfn[u] = low[u] = ++stamp; // stamp 為走訪時間戳
  st.push(u);
  in_st[v] = true; // v 已在 st 中

  for(int v: E[u]) {
    if(dfn[v]) {
      if(in_st[v]) low[u] = min(low[u], dfn[v]);
      continue;
    }

    dfs(v);
    low[u] = min(low[u], low[v]);
  }

  if(low[u] == dfn[u]) { // 符合條件，將子圖分出去
    vector<int> sub; // sub := subgraph
    do {
      int v = st.top(); st.pop();
      in_st[v] = false; // v 移出 st
      sub.push_back(v);
    } while(v != u);

    SCC.push_back(sub);
  }
}

$\text{dfn}(x) = 0$ 表示 $x$ 還未搜索過，所以對於該 $x$ 都要去做 DFS：

for(int u = 0; u < n; u++) if(!dfn[u]) dfs(u); // 節點編號從 0 到 n-1

練習：

:::warning 證明 Tarjan's algorithm for SCCs 不能用 $\text{dep}$ 取代 $\text{dfn}$ ::: :::warning 證明 Tarjan's algorithm for APs 可以用 $\text{dfn}$ 取代 $\text{dep}$ ::: UVa OJ 11838 Come and Go

Lowest Common Ancestor (LCA)

給定一棵樹，若節點 $a$ 滿足其孫子節點有 $u, v$ 或是 $a = u$ 或 $a = v$，則稱 $a$ 為 $u, v$ 的共同祖先 而共同祖先中離根節點最遠或說深度最深的節點稱作 $u, v$ 的最近共同祖先

digraph {
  a -> b
  a -> f
  a -> d -> e
  d -> c
}

如上圖 $e, c$ 的共同祖先有 $a, d$，最近共同祖先為 $d$；而 $a, b$ 的共同祖先為 $a$

:::info 求某節點對的最近共同祖先 (LCA) :::

Tarjan's off-line algorithm for LCA

又是你啊！Tarjan？

以 DFS 這棵樹，走到某節點 $u$ 時，會將一些子樹走訪完，接著再往下個子樹走訪明顯的，走訪完的子樹上的節點與下個子樹上的節點的 LCA 就是 $u$

digraph {
  u -> a -> b
  u -> c -> d
  u -> e -> f -> g
  
  a[style="filled", fillcolor=yellow];
  b[style="filled", fillcolor=yellow];
  c[style="filled", fillcolor=yellow];
  d[style="filled", fillcolor=yellow];
}

如圖，黃色部分是走訪完的子樹，接著要往 $e$ 走訪，那麼 $e, f, g$ 與黃色節點的 LCA 就為 $u$

實作上：

會將遇到的子樹節點都記錄起來，再與下個要走的子樹節點互相配對
使用 Union-Find Forest 查詢走訪完的子樹根節點為何 (就是 LCA)

void dfs(int u = root) {
  for(int v = 0; v < n; v++)
    if(vis[v]) LCA[u][v] = LCA[v][u] = find(v);

  for(int v = 0; v < n; v++) if(E[u][v]) { // 假設此為有向樹
    vis[v] = true;
    dfs(v);
    group[v] = u; // v 子樹都拜訪完就與父節點 u 做 Union
  }
}

這裡 E 是鄰接矩陣，E[a][b] 表示有 a 到 b 的邊

這樣 $O(|V|^2)$ 複雜度就將所有節點對的 LCA 都找完了

練習：

SPOJ POLICEMEN Police Men

Jump-pointer algorithm

digraph {
  a -> b
  a -> f -> d -> h ->e
  d -> c -> i -> g
  
  a[style="filled", fillcolor=maroon1];
  f[style="filled", fillcolor=maroon2];
  d[style="filled", fillcolor=maroon3];
  }

上圖 $e, g$ 的共同祖先有 $a, f, d$，其中 $d$ 是 LCA 可觀察到任意兩節點 $u, v$ 的 LCA 的祖先們一定是 $u, v$ 的共同祖先

於是若 $u, v$ 的深度相同時，讓兩者同時往上走，第一次遇到的共同祖先就是 LCA 而不失一般性若 $u$ 深度大於 $v$，只要先讓 $u$ 往上走到跟 $v$ 相同的深度就行了如上圖欲找 $e, g$ 的 LCA，先讓 $g$ 走到與 $e$ 深度相同的 $i$，接著兩者走到 $h, c$，再走到 $d$

倍增法

又是你啊！？二進制？？

LCA 與兩節點的距離一定是整數，整數可由 $2$ 的幂 ${2^i \mid i \ge 0}$ 獨立⁶和成所以只需將每節點 $2$ 的幂距離的祖先節點記錄起來，再透過這些距離跳到 LCA 就行了

digraph {
  a -> b
  f -> d -> h ->e
  a -> f -> c -> i -> g
  
  a[style="filled", fillcolor=maroon1];
  f[style="filled", fillcolor=maroon2];
  }

如上圖找 $e, g$ 的 LCA，看出距離為 $3 = 2^1 + 2^0$，先以距離 $2^1$ 跳到 $d, c$，再以距離 $2^0$ 跳到 $f$

實作上用陣列值 an[u][i] 表示與 $u$ 距離為 $2^i$ 的祖先節點

memset(an, -1, sizeof an); // 初始 -1 表示該祖先節點可能不存在

將每個節點的深度以及距離 $2^i$ 的祖先節點都記錄起來

void dfs(int u, int d) { // d := depth
  dep[u] = d;
  
  for(int v: E[u]) { // 假設此為有向樹
    an[v][0] = u; // v 的父節點為 u
    for(int i = 1; i <= log2(d+1); i++) // 最高只到根
      if(an[v][i-1] != -1) an[v][i] = an[an[v][i-1]][i-1]; // 倍增距離找祖先

    dfs(v, d+1);
  }
}

接著就能算某節點對 $u,v$ 的 LCA 為何：

int LCA(int u, int v) {
  if(dep[u] < dep[v]) swap(u, v);

  while(dep[u] != dep[v]) { // 將 u 往上跳至 v 同樣深度
    int i = log2(dep[u] - dep[v]);
    u = an[u][i];
  }

  if(u == v) return u;

  for(int i = log2(dep[u]); i >= 0; i--) // 將 u, v 跳至 LCA 下方
    if(an[u][i] != an[v][i]) u = an[u][i], v = an[v][i];

  return an[u][0];
}

練習：

POJ 1330 Nearest Common Ancestors ICPC Regionals 2010 Hangzhou Traffic Real Time Query System TIOJ 1163 6.施工中的道路

Footnotes

所謂的比較高，意思是距離根比較近 ↩
Wikipedia/ A demo of Tarjan's algorithm to find cut vertices. ↩
Wikipedia/ Graph with strongly connected components marked ↩
Wikipedia/ Tarjan's Algorithm Animation ↩
也可以嘗試將搜索到的節點留給 DFS 函數 ↩
每個幂最多取一次 ↩

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

2020_Week_12_Graph.md

2020_Week_12_Graph.md

2020 Week 12: Graph

Articulation point (AP)

Tarjan’s algorithm for APs

練習：

Strongly Connected Components (SCC)

Kosaraju's Algorithm

練習：

Tarjan's algorithm for SCCs

練習：

Lowest Common Ancestor (LCA)

Tarjan's off-line algorithm for LCA

練習：

Jump-pointer algorithm

倍增法

練習：

Files

2020_Week_12_Graph.md

Latest commit

History

2020_Week_12_Graph.md

File metadata and controls

2020 Week 12: Graph

Articulation point (AP)

Tarjan’s algorithm for APs

練習：

Strongly Connected Components (SCC)

Kosaraju's Algorithm

練習：

Tarjan's algorithm for SCCs

練習：

Lowest Common Ancestor (LCA)

Tarjan's off-line algorithm for LCA

練習：

Jump-pointer algorithm

倍增法

練習：

Footnotes