跳转至

強連通分量

簡介

在閲讀下列內容之前，請務必瞭解 圖論相關概念 中的基礎部分。

強連通的定義是：有向圖 G 強連通是指，G 中任意兩個結點連通。

強連通分量（Strongly Connected Components，SCC）的定義是：極大的強連通子圖。

這裏要介紹的是如何來求強連通分量。

Tarjan 算法

引入

Robert E. Tarjan（羅伯特·塔揚，1948~），生於美國加州波莫納，計算機科學家。

Tarjan 發明了很多算法和數據結構。不少他發明的算法都以他的名字命名，以至於有時會讓人混淆幾種不同的算法。比如求各種連通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。並查集、Splay、Toptree 也是 Tarjan 發明的。

我們這裏要介紹的是在有向圖中求強連通分量的 Tarjan 算法。

DFS 生成樹

在介紹該算法之前，先來了解 DFS 生成樹，我們以下面的有向圖為例：

DFS 生成樹

有向圖的 DFS 生成樹主要有 4 種邊（不一定全部出現）：

  1. 樹邊（tree edge）：示意圖中以黑色邊表示，每次搜索找到一個還沒有訪問過的結點的時候就形成了一條樹邊。
  2. 反祖邊（back edge）：示意圖中以紅色邊表示（即 \(7 \rightarrow 1\)），也被叫做回邊，即指向祖先結點的邊。
  3. 橫叉邊（cross edge）：示意圖中以藍色邊表示（即 \(9 \rightarrow 7\)），它主要是在搜索的時候遇到了一個已經訪問過的結點，但是這個結點 並不是 當前結點的祖先。
  4. 前向邊（forward edge）：示意圖中以綠色邊表示（即 \(3 \rightarrow 6\)），它是在搜索的時候遇到子樹中的結點的時候形成的。

我們考慮 DFS 生成樹與強連通分量之間的關係。

如果結點 \(u\) 是某個強連通分量在搜索樹中遇到的第一個結點，那麼這個強連通分量的其餘結點肯定是在搜索樹中以 \(u\) 為根的子樹中。結點 \(u\) 被稱為這個強連通分量的根。

反證法：假設有個結點 \(v\) 在該強連通分量中但是不在以 \(u\) 為根的子樹中，那麼 \(u\) 到 \(v\) 的路徑中肯定有一條離開子樹的邊。但是這樣的邊只可能是橫叉邊或者反祖邊，然而這兩條邊都要求指向的結點已經被訪問過了，這就和 \(u\) 是第一個訪問的結點矛盾了。得證。

Tarjan 算法求強連通分量

在 Tarjan 算法中為每個結點 \(u\) 維護了以下幾個變量：

  1. \(\textit{dfn}_u\)：深度優先搜索遍歷時結點 \(u\) 被搜索的次序。
  2. \(\textit{low}_u\)：在 \(u\) 的子樹中能夠回溯到的最早的已經在棧中的結點。設以 \(u\) 為根的子樹為 \(\textit{Subtree}_u\)。\(\textit{low}_u\) 定義為以下結點的 \(\textit{dfn}\) 的最小值：\(\textit{Subtree}_u\) 中的結點；從 \(\textit{Subtree}_u\) 通過一條不在搜索樹上的邊能到達的結點。

一個結點的子樹內結點的 dfn 都大於該結點的 dfn。

從根開始的一條路徑上的 dfn 嚴格遞增，low 嚴格非降。

按照深度優先搜索算法搜索的次序對圖中所有的結點進行搜索，維護每個結點的 dfn 與 low 變量，且讓搜索到的結點入棧。每當找到一個強連通元素，就按照該元素包含結點數目讓棧中元素出棧。在搜索過程中，對於結點 \(u\) 和與其相鄰的結點 \(v\)（\(v\) 不是 \(u\) 的父節點）考慮 3 種情況：

  1. \(v\) 未被訪問：繼續對 \(v\) 進行深度搜索。在回溯過程中，用 \(\textit{low}_v\) 更新 \(\textit{low}_u\)。因為存在從 \(u\) 到 \(v\) 的直接路徑，所以 \(v\) 能夠回溯到的已經在棧中的結點，\(u\) 也一定能夠回溯到。
  2. \(v\) 被訪問過，已經在棧中：根據 low 值的定義，用 \(\textit{dfn}_v\) 更新 \(\textit{low}_u\)。
  3. \(v\) 被訪問過，已不在棧中：説明 \(v\) 已搜索完畢，其所在連通分量已被處理，所以不用對其做操作。

將上述算法寫成偽代碼：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been searched then
            TARJAN_SEARCH(v) // 搜索
            low[u]=min(low[u],low[v]) // 回溯
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

對於一個連通分量圖，我們很容易想到，在該連通圖中有且僅有一個 \(u\) 使得 \(\textit{dfn}_u=\textit{low}_u\)。該結點一定是在深度遍歷的過程中，該連通分量中第一個被訪問過的結點，因為它的 dfn 和 low 值最小，不會被該連通分量中的其他結點所影響。

因此，在回溯的過程中，判定 \(\textit{dfn}_u=\textit{low}_u\) 是否成立，如果成立，則棧中 \(u\) 及其上方的結點構成一個 SCC。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 結點 i 所在 SCC 的編號
int sz[N];       // 強連通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
dfn = [0] * N; low = [0] * N; dfncnt = 0; s = [0] * N; in_stack  = [0] * N; tp = 0
scc = [0] * N; sc = 0 # 結點 i 所在 SCC 的編號
sz = [0] * N # 強連通 i 的大小
def tarjan(u):
    low[u] = dfn[u] = dfncnt; s[tp] = u; in_stack[u] = 1
    dfncnt = dfncnt + 1; tp = tp + 1
    i = h[u]
    while i:
        v = e[i].t
        if dfn[v] == False:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif in_stack[v]:
            low[u] = min(low[u], dfn[v])
        i = e[i].nex
    if dfn[u] == low[u]:
        sc = sc + 1
        while s[tp] != u:
            scc[s[tp]] = sc
            sz[sc] = sz[sc] + 1
            in_stack[s[tp]] = 0
            tp = tp - 1
        scc[s[tp]] = sc
        sz[sc] = sz[sc] + 1
        in_stack[s[tp]] = 0
        tp = tp - 1

時間複雜度 \(O(n + m)\)。

Kosaraju 算法

引入

Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未發表的論文上提出，但 Micha Sharir 最早發表了它。

過程

該算法依靠兩次簡單的 DFS 實現：

第一次 DFS，選取任意頂點作為起點，遍歷所有未訪問過的頂點，並在回溯之前給頂點編號，也就是後序遍歷。

第二次 DFS，對於反向後的圖，以標號最大的頂點作為起點開始 DFS。這樣遍歷到的頂點集合就是一個強連通分量。對於所有未訪問過的結點，選取標號最大的，重複上述過程。

兩次 DFS 結束後，強連通分量就找出來了，Kosaraju 算法的時間複雜度為 \(O(n+m)\)。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// g 是原圖，g2 是反圖

void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) dfs1(v);
  s.push_back(u);
}

void dfs2(int u) {
  color[u] = sccCnt;
  for (int v : g2[u])
    if (!color[v]) dfs2(v);
}

void kosaraju() {
  sccCnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);
  for (int i = n; i >= 1; --i)
    if (!color[s[i]]) {
      ++sccCnt;
      dfs2(s[i]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def dfs1(u):
    vis[u] = True
    for v in g[u]:
        if vis[v] == False:
            dfs1(v)
    s.append(u)

def dfs2(u):
    color[u] = sccCnt
    for v in g2[u]:
        if color[v] == False:
            dfs2(v)

def kosaraju(u):
    sccCnt = 0
    for i in range(1, n + 1):
        if vis[i] == False:
            dfs1(i)
    for i in range(n, 0, -1):
        if color[s[i]] == False:
            sccCnt = sccCnt + 1
            dfs2(s[i])

Garbow 算法

過程

Garbow 算法是 Tarjan 算法的另一種實現，Tarjan 算法是用 dfn 和 low 來計算強連通分量的根，Garbow 維護一個節點棧，並用第二個棧來確定何時從第一個棧中彈出屬於同一個強連通分量的節點。從節點 \(w\) 開始的 DFS 過程中，當一條路徑顯示這組節點都屬於同一個強連通分量時，只要棧頂節點的訪問時間大於根節點 \(w\) 的訪問時間，就從第二個棧中彈出這個節點，那麼最後只留下根節點 \(w\)。在這個過程中每一個被彈出的節點都屬於同一個強連通分量。

當回溯到某一個節點 \(w\) 時，如果這個節點在第二個棧的頂部，就説明這個節點是強連通分量的起始節點，在這個節點之後搜索到的那些節點都屬於同一個強連通分量，於是從第一個棧中彈出那些節點，構成強連通分量。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int garbow(int u) {
  stack1[++p1] = u;
  stack2[++p2] = u;
  low[u] = ++dfs_clock;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!low[v])
      garbow(v);
    else if (!sccno[v])
      while (low[stack2[p2]] > low[v]) p2--;
  }
  if (stack2[p2] == u) {
    p2--;
    scc_cnt++;
    do {
      sccno[stack1[p1]] = scc_cnt;
      // all_scc[scc_cnt] ++;
    } while (stack1[p1--] != u);
  }
  return 0;
}

void find_scc(int n) {
  dfs_clock = scc_cnt = 0;
  p1 = p2 = 0;
  memset(sccno, 0, sizeof(sccno));
  memset(low, 0, sizeof(low));
  for (int i = 1; i <= n; i++)
    if (!low[i]) garbow(i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def garbow(u):
    stack1[p1] = u
    stack2[p2] = u
    p1 = p1 + 1; p2 = p2 + 1
    low[u] = dfs_clock
    dfs_clock = dfs_clock + 1
    i = head[u]
    while i:
        v = e[i].to
        if low[v] == False:
            garbow(v)
        elif sccno[v] == False:
            while low[stack2[p2]] > low[v]:
                p2 = p2 - 1
    if stack2[p2] == u:
        p2 = p2 - 1
        scc_cnt = scc_cnt + 1
        while stack1[p1] != u:
            p1 = p1 - 1
            sccno[stack1[p1]] = scc_cnt

def find_scc(n):
    dfs_clock = scc_cnt = 0
    p1 = p2 = 0
    sccno = []; low = []
    for i in range(1, n + 1):
        if low[i] == False:
            garbow(i)

應用

我們可以將一張圖的每個強連通分量都縮成一個點。

然後這張圖會變成一個 DAG，可以進行拓撲排序以及更多其他操作。

舉個簡單的例子，求一條路徑，可以經過重複結點，要求經過的不同結點數量最多。

習題

USACO Fall/HAOI 2006 受歡迎的牛

POJ1236 Network of Schools

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用