Graph: 利用DFS尋找Strongly Connected Component(SCC)

先備知識與注意事項

在一個directed graph中，若對於任意兩個vertex(A)與vertex(B)之間，不是同時存在「從vertex(A)走到vertex(B)」以及「從vertex(B)走到vertex(A)」的path，那麼此directed graph就不是strongly connected，裡面一定包含了兩個以上的strongly connected component(SCC)。

如圖一(a)，經由path:0-1-2-5，可以從vertex(0)走到vertex(5)，但是無論經過任何vertex，都沒有辦法從vertex(5)走到vertex(0)，因此，圖一(a)的directed graph並不是strongly connected，其中包含了兩個以上的SCC(答案是三個)。

圖一(a)。

那麼，要如何分辨一個directed graph中的strongly connected component(SCC)，並列出每一個SCC中的所有vertex呢？

本篇文章的目的就是要回應此問題。

演算法將會用到Transpose of Graph，如圖一(b)，把G中所有vertex維持不變，edge的方向顛倒，就得到G^T，例如，原本的edge(0,1)改為edge(1,0)，edge(5,6)改為edge(6,5)。

圖一(b)。

最重要的是：G與G^T的SCC完全相同。

原因在於，觀察G中包含在同一個SCC裡的vertex(2)與vertex(3)。G中同時存在「從vertex(2)走到vertex(3)」的path，以及「從vertex(3)走到vertex(2)」的path。在G進行「Transpose」得到G^T後，這兩條path分別變成與原方向之相反方向，但是存在於vertex(2)與vertex(3)之間的cycle仍然存在。
因此，在G裡面屬於同一個SCC的vertex，在G^T裡將形成相同的SCC。

最後一點溫馨小提醒：一如往常，本篇文章將不會有嚴謹證明，不過在參考資料會附上內有嚴謹證明的網站連結，請讀者務必前往一窺究竟。

如果只有一次DFS不行嗎？

在上一篇文章提到，只用一次DFS()或BFS()得到predecessor後，便能夠找到undirected graph中的connected component。

那如果用來找SCC？

以下示範兩次DFS()來說明，一次是按照「\(8、7、...、2、1\)」之順序把vertex設為搜尋起點，另一次則是按照「\(1、2、...、7、8\)」之順序。

圖二(a)：以vertex(8)作為起點，接著是vertex(5)、vertex(3)。

圖二(a)，首先以vertex(8)作為DFS()的第一次起點，在搜尋完以vertex(8)作為root的Depth-First Tree後，再以vertex(5)作為新的起點。同樣的，在搜尋完以vertex(5)作為root的Depth-First Tree後，再以vertex(3)作為新的起點。
從圖二(a)的「時間軸」可以看出，此次DFS()找到了一個Depth-First Forest，其中包含三棵Depth-First Tree，而這三棵Depth-First Tree分別就是Graph中的三個SCC。

問題不就解決了嗎？
透過一次DFS()就找到了directed graph中的SCC。

再接著看圖二(b)，以vertex(0)作為DFS()的起點。
很遺憾，「時間軸」裡形成了一整棵Depth-First Tree，directed graph中的三個SCC沒有被分開。

圖二(b)：以vertex(0)作為起點。

由於SCC需要兩個方向的path(「vertex(X)到vertex(Y)」和「vertex(Y)到vertex(X)」)都成立，但是DFS()只在意「單方向」的edge，只要存在edge(X,Y)，便把predecessor[Y]更新成vertex(X)，在Predecessor Subgraph裡，vertex(X)與vertex(Y)便在同一棵Depth-First Tree中。

因此，只有一次DFS()的predecessor是不夠的，圖二(a)只是運氣好。

以下便開始本次的「拒絕運氣好大作戰」。

演算法

若考慮具有多個SCC的directed graph，為了方便起見，定義其Component Graph為\(G^{SCC}=(V^{SCC},E^{SCC})\)，其中：

\(V^{SCC}\)：把每個SCC視為一個元素，並以該元素作為\(V^{SCC}\)的vertex。
- 例如圖三(a)，令\(C_1=\){\(0,1,2,3\)}，\(C_2=\){\(4,5\)}，\(C_3=\){\(6,7,8\)}，則\(V^{SCC}=\){\(C_1,C_2,C_3\)}。
\(E^{SCC}\)：考慮vertex(X)屬於\(C_1\)，vertex(Y)屬於\(C_2\)，若存在「連結兩個不同SCC」的edge(X,Y)，則edge(X,Y)便屬於\(E^{SCC}\)。
- 以圖三(a)為例，vertex(1)屬於\(C_1\)，vertex(4)屬於\(C_2\)，則edge(1,4)屬於\(E^{SCC}\)，依此類推，便得到\(E^{SCC}=\){\((1,4),(2,5),(4,6),(5,6),(5,7)\)}。

圖三(a)：每一個directed graph，只要「以SCC作為基本元素(vertex)」，都會有其相對應的component graph。

由上述定義可以觀察出，每一個directed graph，只要「以SCC作為基本元素(vertex)」，都會有其相對應的component graph。

而使用component graph的優點是：「component graph一定是directed acyclic graph(DAG)」。

因為SCC的定義(請參閱：Graph: Intro(簡介))，若C₁與C₂之前存在cycle，那就表示C₁和C₂都不應該自稱為SCC，而要合併C₁與C₂成為一個更大集合的SCC。因此，不同的SCC之間，一定不存在cycle。
等價的性質：若directed graph中存在兩個SCC，分別為C₁與C₂，若存在一條path從C₁中的vertex(X)走到C₂中的vertex(Y)，就不可能同時存在一條path從C₂中的vertex(Z)走到C₁中的vertex(W)，否則即出現cycle，應該合併成更大的SCC(C₃)，如圖三(b)。

圖三(b)：SCC。

考慮如圖三(c)的DAG(directed acyclic graph)，若DFS()在每次尋找「新的搜尋起點時」，能夠按照「一條path上，從尾端至開頭」的vertex順序，那麼Predecessor Subgraph就能長成「能夠分辨出SCC」的Depth-First Forest。

圖三(c)中，由於從C₃無法往回走到C₂，從C₂無法往回走到C₁，因此，DFS()的起點順序若為：C₃、C₂、C₁，就能夠把這三個component graph中的vertex(也就是directed graph的SCC)給分開。

圖三(c)：。

那麼，該如何確保每一次都能找到「一條path上，從尾端至開頭的vertex順序」？

圖三(d)：。

再觀察圖三(d)，分別以起點順序「C₂、C₃、C₁」與起點順序「C₁、C₂、C₃」進行DFS()，配合圖三(c)，將發現，不論以哪個vertex作為起點，「finish的大小順序一定是C₁、C₂、C₃」。

更廣義地，假設現有C₁與C₂分別為directed graph中兩個互斥(disjoint)的SCC，並且vertex(X)屬於C₁，vertex(Y)屬於C₂：

若directed graph中存在edge(X,Y)，那麼，C₁集合中所有vertex的「最大finish」一定比C₂集合中所有vertex的「最大finish」還要大。

以圖三(e)為例，component graph的\(E^{SCC}\)存在「從C₁指向C₂」以及「從C₂指向C₃」的edge，因此，若以SCC中vertex的「最大finish」代表finish[SCC]，finish的大小順序應為：finish[C1]>finish[C2]>finish[C3]，其中：

\(C_1=\){\(0,1,2,3\)}，finish[C1]\(=\)finish[3]\(=18\)。
\(C_2=\){\(4,5\)}，finish[C2]\(=\)finish[5]\(=10\)。
\(C_3=\){\(6,7,8\)}，finish[C3]\(=\)finish[8]\(=6\)。

圖三(e)：。

考慮圖三(f)，仍然符合：finish[C1]>finish[C2]>finish[C3]：

finish[C1]\(=\)finish[0]\(=18\)。
finish[C2]\(=\)finish[5]\(=15\)。
finish[C3]\(=\)finish[6]\(=13\)。

圖三(f)：。

由以上推論，可以更新在圖三(c)時的說明至更廣義的結論：

只要按照「finish小到大」的順序選取SCC中的vertex作為DFS()的起點，就能夠在Predecessor Subgraph中以Depth-First Forest分辨出所有SCC。

到這裡為止，可以確認：

需要第一次DFS()先取得finish。
再根據剛取得的finish之「順序」來判斷「第二次DFS()」的起點順序。
進行第二次DFS()來取得predecessor，並利用Predecessor Subgraph分辨出SCC。

但是問題又來了。
如果真的是按照「第一次finish由小到大」的順序選取SCC中的vertex作為第二次DFS()的起點，還是有可能失敗，因為第一次DFS()在選取起點時，並沒有對SCC的先備知識，可以視為隨機選取：

若第一次DFS()結果如圖三(e)，則按照「finish由小到大」的順序選取起點，將依序選中「vertex(7)、vertex(4)、vertex(1)」作為起點進行第二次DFS()，那麼將得到如圖三(g)之結果，順利區分三個SCC。

圖三(g)：。

但是如果第一次DFS()結果如圖三(f)，按照「finish由小到大」的順序選取起點，只會選中vertex(3)作為起點，便把整個Graph搜尋完畢，最後Predecessor Subgraph又形成一整棵Depth-First Tree，如圖三(h)。

圖三(h)：。

所以，先在Graph:G上執行第一次DFS()，得到finish後，按照finish由小到大的順序，作為第二次在Graph:G上執行DFS()的起點之方法，宣告失敗。

不過，還好有Transpose of Graph: G^T。

圖三(i)：。

觀察圖三(i)中的G與G^T，發現：

兩個Graph的SCC完全相同，皆為C₁、C₂、C₃。
SCC的finish順序完全相反。
- 在G上，從C₃無法往回走到C₂，從C₂無法往回走到C₁。
- 在G^T上，從C₁無法往回走到C₂，從C₂無法往回走到C₃。

根據以上特徵，若先在Graph:G上執行第一次DFS()，得到finish後，按照finish由大到小的順序，會是「C₁、C₂、C₃」，而這個順序在Transpose of Graph: G^T，就正好是「finish小到大」的順序。

因此，以「第一次DFS()所得到的finish之由大到小順序」選取起點，在G^T上進行第二次DFS()，就可以先選到C₁，由於無法從C₁走回C₂，因此DFS()在搜尋完C₁內的所有vertex後，便形成自己的Depth-First Tree。接著再依序挑選C₂、C₃為起點進行搜尋，並且建立起各自SCC的Depth-First Tree。

如此一來，便找到了directed graph中的SCC。

程式碼

根據以上說明，演算法分成四個步驟：

對G執行DFS()。
產生G^T。
按照第一次DFS()所得到的finish由大到小的順序選取起點，對G^T執行DFS()。
從第二次DFS()的predecessor找到Predecessor Subgraph。若directed graph有多個SCC，那麼Predecessor Subgraph就會是Depth-First Forest，其中的每一棵Depth-First Tree都是一個SCC。

範例程式碼延續上一篇文章定義的class Graph，主要多了幾個函式：

GetColor()、GetFinish()、GetPredecessor：用來取得color、finish、predecessor。
GraphTranspose()：產生G^T。
VariableInitializeDFS()：把原先DFS()主函式中，「配置記憶體」與「初始化」資料的部分獨立出來。
QuickSort()等三個函式：用來得到finish由大致小的vertex順序。
- 若共有6個vertex，經過一次DFS()後得到finish如圖四，那麼QuickSort()將會對finish進行排序，並且在排序的過程，一併將finish原先對應的vertex排序後，放入finishLargetoSmall。之後再利用finishLargetoSmall的順序，進行第二次DFS()。
PrintSCCs()：尋找SCC最主要的函式，主要包含上述的四個步驟。(其中有許多用以顯示資料項的指令，與尋找SCC無關)

圖四：。

// C++ code
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>      // for std::setw()

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *predecessor,
        *distance,          // for BFS()
        *discover,          // for DFS()
        *finish;
public:
    Graph():num_vertex(0){};
    Graph(int N):num_vertex(N){
        // initialize Adj List
        AdjList.resize(num_vertex);
    };

    int GetColor(int i){return color[i];};              // 取得private data: color
    int GetFinish(int i){return finish[i];};            // 取得private data: finish
    int GetPredecessor(int i){return predecessor[i];};  // 取得private data: predecessor

    void AddEdgeList(int from, int to);

    void BFS(int Start);
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);
    void VariableInitializeDFS();     // 對DFS()需要的資料：color, discover, finish, predecessor
                                      // 進行「配置記憶體」與「初始化」

    void CCDFS(int vertex);           // 吃一個int, 表示起點vertex, 若沒給就從0開始
    void CCBFS(int vertex = 0);
    void SetCollapsing(int vertex);
    void PrintDataArray(int *array);  // 列印出array[]
    void PrintFinish();               // 列印出 finish[]
    void PrintPredecessor();          // 列印出 predecessor[]

    Graph GraphTranspose();           // 產生Transpose of Graph
    void PrintSCCs(int Start = 0);    // 吃一個int, 表示起點vertex, 若沒給就從0開始

    // 利用QuickSort()得到 finish[] 由大致小的vertex順序
    friend void QuickSort(int *vec, int front, int end, int *vec2);
    friend int Partition(int *vec, int front, int end, int *vec2);
    friend void swap(int *x, int *y);
};

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}
int Partition(int *vec, int front, int end, int *vec2){
    int pivot = vec[end];
    int i = front - 1;
    for (int j = front; j < end; j++) {
        if (vec[j] > pivot) {
            i++;
            swap(&vec[i], &vec[j]);
            swap(&vec2[i], &vec2[j]);
        }
    }
    swap(&vec[i + 1], &vec[end]);
    swap(&vec2[i + 1], &vec2[end]);

    return i + 1;   // 把 i + 1 當成下一個 recurrsive call 的 中間斷點
}
void QuickSort(int *vec, int front, int end, int *vec2){
    if (front < end) {
        int pivot = Partition(vec, front, end, vec2);
        QuickSort(vec, front, pivot - 1, vec2);
        QuickSort(vec, pivot + 1, end, vec2);
    }
}

void Graph::PrintSCCs(int Start){
    // 第一次DFS(), 目的是取得finish[]
    DFS(Start);

    // 顯示 第一次DFS()後的finish[]
    std::cout << "First DFS() on G, finish time:" << std::endl;
    PrintFinish();

    // gT代表Transpose of Graph
    Graph gT(num_vertex);
    gT = GraphTranspose();

    // 矩陣 finishLargetoSmall[] 用來儲存 finish[] 由大至小的vertex順序
    int finishLargetoSmall[num_vertex];
    for (int i = 0; i < num_vertex; i++) {
        finishLargetoSmall[i] = i;
    }
    // QuickSort()會更新 finishLargetoSmall[] 成 finish[] 由大至小的vertex順序
    QuickSort(finish, 0, num_vertex-1, finishLargetoSmall);

    // 列印出 finish[] 由大至小的vertex順序
    std::cout << "finish time Large to Small:" << std::endl;
    PrintDataArray(finishLargetoSmall);

    // 第二次DFS(), 執行在gT上, 先對四個資料「配置記憶體」且「初始化」
    gT.VariableInitializeDFS();
    int time = 0;
    for (int i = 0; i < num_vertex; i++){
        if (gT.GetColor(finishLargetoSmall[i]) == 0) {
            gT.DFSVisit(finishLargetoSmall[i], time);
        }
    }

    // 顯示 第二次DFS()後的finish[]
    std::cout << "Second DFS() on gT, finish time:\n";
    gT.PrintFinish();
    // 顯示 第二次DFS()後的predecessor[]
    std::cout << "predecessor[] before SetCollapsing:\n";
    gT.PrintPredecessor();

    for (int i = 0; i< num_vertex; i++)
        gT.SetCollapsing(i);

    // 顯示 SetCollapsing後的predecessor[]
    std::cout << "predecessor after SetCollapsing:\n";
    gT.PrintPredecessor();

    // 如同在undirected graph中尋找connected component
    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (gT.GetPredecessor(i) < 0) {
            std::cout << "SCC#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (gT.GetPredecessor(j) == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
    std::cout << std::endl;
}
void Graph::VariableInitializeDFS(){
    color = new int[num_vertex];
    discover = new int[num_vertex];
    finish = new int[num_vertex];
    predecessor = new int[num_vertex];

    for (int i = 0; i < num_vertex; i++) {
        color[i] = 0;
        discover[i] = 0;
        finish[i] = 0;
        predecessor[i] = -1;
    }
}
Graph Graph::GraphTranspose(){
    Graph gT(num_vertex);
    for (int i = 0; i < num_vertex; i++) {
        for (std::list<int>::iterator itr = AdjList[i].begin();itr != AdjList[i].end(); itr++) {
            gT.AddEdgeList(*itr, i);
        }
    }
    return gT;
}
void Graph::PrintDataArray(int *array){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << array[i];
    std::cout << std::endl;
}
void Graph::PrintFinish(){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << finish[i];
    std::cout << std::endl;
}
void Graph::PrintPredecessor(){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << predecessor[i];
    std::cout << std::endl;
}

int main(){
    Graph g4(9);
    g4.AddEdgeList(0, 1);
    g4.AddEdgeList(1, 2);g4.AddEdgeList(1, 4);
    g4.AddEdgeList(2, 0);g4.AddEdgeList(2, 3);g4.AddEdgeList(2, 5);
    g4.AddEdgeList(3, 2);
    g4.AddEdgeList(4, 5);g4.AddEdgeList(4, 6);
    g4.AddEdgeList(5, 4);g4.AddEdgeList(5, 6);g4.AddEdgeList(5, 7);
    g4.AddEdgeList(6, 7);
    g4.AddEdgeList(7, 8);
    g4.AddEdgeList(8, 6);

    std::cout << "Vertex(0) as starting point for the First DFS():\n\n";
    g4.PrintSCCs();
    std::cout << "Vertex(3) as starting point for the First DFS():\n\n";
    g4.PrintSCCs(3);

    return 0;
}

output:

Vertex(0) as starting point for the First DFS():

First DFS() on G, finish time:
   0   1   2   3   4   5   6   7   8
  18  17  16   5  14  15  13  12  11
finish time Large to Small:
   0   1   2   3   4   5   6   7   8
   0   1   2   5   4   6   7   8   3
Second DFS() on gT, finish time:
   0   1   2   3   4   5   6   7   8
   8   4   7   6  11  12  18  16  17
predecessor[] before SetCollapsing:
   0   1   2   3   4   5   6   7   8
  -1   2   0   2   5  -1  -1   8   6
predecessor after SetCollapsing:
   0   1   2   3   4   5   6   7   8
  -1   0   0   0   5  -1  -1   6   6
SCC#1: 0 1 2 3 
SCC#2: 5 4 
SCC#3: 6 7 8 

Vertex(3) as starting point for the First DFS():

First DFS() on G, finish time:
   0   1   2   3   4   5   6   7   8
  16  15  17  18  14  13  12  11  10
finish time Large to Small:
   0   1   2   3   4   5   6   7   8
   3   2   0   1   4   5   6   7   8
Second DFS() on gT, finish time:
   0   1   2   3   4   5   6   7   8
   5   6   7   8  12  11  18  16  17
predecessor[] before SetCollapsing:
   0   1   2   3   4   5   6   7   8
   1   2   3  -1  -1   4  -1   8   6
predecessor after SetCollapsing:
   0   1   2   3   4   5   6   7   8
   3   3   3  -1  -1   4  -1   6   6
SCC#1: 3 0 1 2 
SCC#2: 4 5 
SCC#3: 6 7 8