Graph: 利用DFS和BFS尋找Connected Component

Posted by Chiu CC on 2 12, 2016


先備知識與注意事項

在一個undirected graph中,若存在任意兩個vertex之間不具有path連結,那麼此undirected graph就不是connected,裡面一定包含了兩個以上的connected component。

如圖一(a),vertex(0)與vertex(1)不論經過Graph中其他任何vertex都沒有辦法產生一條path連結,則此Graph就不是connected。
並且觀察,vertex(0)、vertex(2)、vertex(4)彼此皆有path能夠互相連結,因此subgraph:\(G(V_1,E_1)\),其中\(V_1=\){\(0,2,4\)}與\(E_1=\){\((0,2),(0,4)\)}即為一個connected component;subgraph:\(G(V_2,E_2)\),其中\(V_2=\){\(1,3\)}與\(E_2=\){\((1,3)\)}是另一個connected component。

cc

圖一(a)。

再看圖一(b),Graph中的任何vertex皆能經由一條path通往其餘vertex,因此,整個Graph所形成的集合即為一個connected component。

cc

圖一(b)。

本篇文章要示範強大的DFS()BFS()的小小應用:尋找undirected graph中的connected component
若不太熟悉connected的定義,可以先閱讀Graph: Intro(簡介)稍稍複習。
此外,為了集中火力,DFS()BFS()的程式碼就留在Graph: Depth-First Search(DFS,深度優先搜尋)Graph: Breadth-First Search(BFS,廣度優先搜尋)裡面,如果還沒有對兩個演算法送出交友邀請,千萬不要客氣。

最後一點溫馨小提醒:Graph與connected component的本質上是Set(集合),因此,以下將會用到Set的觀點做說明。如果不熟悉Set也沒關係,只要知道Set是「一團不在意次序(order)的資料」就可以了。


目錄


DFS與BFS何德何能?

關鍵就是,兩個演算法都能產生predecessor

若vertex(Y)的predecessor[Y]是vertex(X),表示:

  • vertex(Y)是被vertex(X)給找到。
  • 也就表示,在undirected graph中,存在edge(X,Y)。
  • 又因為是undirected graph,若存在edge(X,Y),就能從vertex(X)走到vertex(Y),也能從vertex(Y)走到vertex(X)。

因此,若vertex(Y)的predecessor[Y]是vertex(X),就表示vertex(X)與vertex(Y)一定在同一個connected component裡面。

這也就是為什麼DFS()BFS()都能夠用來尋找undirected graph中的connected component的原因。


演算法

尋找connected component的演算法很直觀,只要三步驟:

  1. 在Graph上執行DFS()BFS()得到predecessor
  2. 進行SetCollapsing()。(蛤?)
  3. 印出共有幾個connected component,以及各個connected component中的vertex。

以上步驟,顯然有個傢伙很突兀。

sc

圖二。

SetCollapsing()是稍後會用到的函式,其功能可以拆成兩個部分理解:一個是「Set」,一個是「Collapsing」:

  • Set(集合):SetCollapsing()處理的對象是Set,也就是不具「次序(order)」的資料,如圖二左,共有三個Set,分別是\(S_1=\){\(0,1,4,5,7\)}、\(S_2=\){\(3,6,8\)}、\(S_3=\){\(2\)}。
    • 在Set上,時常要做的操作便是「查看某個元素(element)在哪一個Set裡面」,而Set通常是用root代表,因此,若如圖二左的方式,以element(0)作為「存取點」(也就是這個Set的root),那麼要判斷element(7)是在element(0)所代表的Set內(而不是element(3)所代表的Set),就需要\(O(N)\)的搜尋時間(\(N\)為Set內的元素數量),從element(7)一路找到element(0),才能判斷。
    • 如果能夠以圖二右的資料結構表示Set,那麼以element(0)、element(2)、element(3)代表Set,要判斷任何一個元素(element)是屬於哪一個Set,便只要\(O(1)\)的時間。
  • Collapsing(塌陷):讓Set「塌陷」,使得所有element皆能直接指向其所在的Set之root

(以下先以DFS()為例,稍後在程式碼的部分將會同步展示以BFS()進行之結果)

考慮圖三(a)的undirected graph:

dfs

圖三(a)。

首先,對Graph進行DFS(),取得predecessor,以及圖三(b)的Depth-First Forest:

  • 由於是undirected graph,由任意vertex作為DFS()起點,結果都會相同。此處以vertex(0)作為起點。
  • 圖三(b)中,vertex(0)、vertex(2)、vertex(3)的predecessor皆為\(-1\),表示這三者皆為Depth-First Tree的root,也就是Set的root
  • 而其餘的vertex,皆能透過predecessor回溯到root

sc

圖三(b)。

接下來要進行SetCollapsing()
在此先以\(Set\):{\(0,1,4,5,7\)}為例作說明,目標是從圖三(c)左轉換成圖三(c)右。

sc

圖三(c)。

先觀察:SetCollapsing()什麼時候完成?
就是當Set中,除了root之外的所有vertex(等義於element)的predecessor都指向root時,也就是當要被「塌陷」的vertex剩下root的時候,SetCollapsing()便完成。

若現在要對vertex(7)進行SetCollapsing(),見圖三(d):

  • 把vertex(7)標記上current
  • 找到vertex(7)所在的Set的root,也就是vertex(0),標記上root
  • 找到vertex(7)的predecessor,也就是vertex(5),標記上parent

接著判斷,若current不等於root(表示除了root之外,還有vertex還沒有「塌陷」,因此SetCollapsing()還沒有完成),那麼就把:

  • currentpredecessor更新成rootpredecessor[7]更新成vertex(0)。
  • 並且把原先的parent當成新的currentcurrent移動到vertex(5)。

sc

圖三(d)。

現在current變成了vertex(5),不等於rootvertex(0),因此繼續:

  • parent標記成vertex(4)。
  • currentpredecessor更新成rootpredecessor[5]更新成vertex(0)。
  • 並且把原先的parent當成新的currentcurrent移動到vertex(4)。

sc

圖三(e)。

接下來的current依序會是vertex(4)、vertex(1),因為current還不是vertex(0),便按照上述步驟「塌陷」。直到current移到vertex(0)後,SetCollapsing()便完成,見圖三(f)。

sc

圖三(f9)。

比較一下經過SetCollapsing()處立前後的predecessor,如圖四。

sc

圖四。

只要先找到predecessor為「負值」的vertex,就找到了代表某一connected component的Set之root,再尋找哪些vertex的predecessor指向該root,便能找出該connected component所包含的所有vertex。

大功告成。


程式碼

範例程式碼除了已經介紹過的class GraphDFS()以及BFS()之外,還多了四個函式。
其中,在undirected graph中尋找connected component的主要函式:CCDFS(int vertex)CCBFS(int vertex)共包含三個部分:

  • DFS()或者BFS(),取得predecessor
  • SetCollapsing是為了讓尋找connected component變得更簡單。
  • 最後,是利用「塌陷」過後的predecessor找到connected component。
    (PrintPredecessor()是為了印出predecessor以驗證SetCollapsing的正確性,非必要。)
// 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);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);    
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);

    void CCDFS(int vertex);                // 利用DFS 
    void CCBFS(int vertex = 0);            // 利用BFS, 兩者邏輯完全相同
    void SetCollapsing(int vertex);
    void PrintPredecessor();               // 印出predecessor, 供驗証用, 非必要
};

void Graph::SetCollapsing(int current){
    int root;  // root
    for (root = current; predecessor[root] >= 0; root = predecessor[root]);

    while (current != root) {
        int parent = predecessor[current];
        predecessor[current] = root;
        current = parent;
    }
}

void Graph::CCDFS(int vertex = 0){

    DFS(vertex);      // 
    PrintPredecessor();
    for (int i = 0; i< num_vertex; i++){
        SetCollapsing(i);
    }
    PrintPredecessor();

    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (predecessor[i] < 0) {
            std::cout << "Component#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (predecessor[j] == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
}

void Graph::CCBFS(int vertex){

    BFS(vertex);
    PrintPredecessor();
    for (int i = 0; i< num_vertex; i++){
        SetCollapsing(i);
    }
    PrintPredecessor();

    int num_cc = 0;
    for (int i = 0; i < num_vertex; i++) {
        if (predecessor[i] < 0) {
            std::cout << "Component#" << ++num_cc << ": " << i << " ";
            for (int j = 0; j < num_vertex; j++) {
                if (predecessor[j] == i) {
                    std::cout << j << " ";
                }
            }
            std::cout << std::endl;
        }
    }
}
void Graph::PrintPredecessor(){
    std::cout << "predecessor:" << std::endl;
    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 g3(9);
    g3.AddEdgeList(0, 1);
    g3.AddEdgeList(1, 0);g3.AddEdgeList(1, 4);g3.AddEdgeList(1, 5);
    // AdjList[2] empty
    g3.AddEdgeList(3, 6);
    g3.AddEdgeList(4, 1);g3.AddEdgeList(4, 5);
    g3.AddEdgeList(5, 1);g3.AddEdgeList(5, 4);g3.AddEdgeList(5, 7);
    g3.AddEdgeList(6, 3);g3.AddEdgeList(6, 8);
    g3.AddEdgeList(7, 5);
    g3.AddEdgeList(8, 6);

    g3.CCDFS();
    std::cout << std::endl;
    g3.CCBFS();
    std::cout << std::endl;

    return 0;
}

output:

predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   1   4   3   5   6
predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   0   0   3   0   3
Component#1: 0 1 4 5 7 
Component#2: 2 
Component#3: 3 6 8 

predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   1   1   3   5   6
predecessor:
   0   1   2   3   4   5   6   7   8
  -1   0  -1  -1   0   0   3   0   3
Component#1: 0 1 4 5 7 
Component#2: 2 
Component#3: 3 6 8 

聰明的讀者們一定已經發現了,不進行SetCollapsing(),單單只靠predecessor一樣可以找出connected component。

不過筆者認為使用SetCollapsing()處理predecessor,雖然不見得是最有效率的方法,但是概念上比較直觀,因為connected component就是Set。

事實上,這兩種Set表示法(「塌陷」前後的predecessor),正好是在Set問題中永恆的兩難(trade-off):「要Union方便」還是「Find方便」,有興趣的讀者可以看看這篇:Disjoint Set Union (Union Find)


如果是Strongly Connected Component呢?

以上處理的是「在undirected graph中尋找connected component」,那如果要在「directed graph中尋找strongly connected component」呢?

顯然,光是只有predecessor是不夠的,因為在directed graph中,predecessor能夠保證的是一個「有方向性」的edge,例如edge(X,Y)表示,從vertex(X)能夠走到vertex(Y),卻不能打包票從vertex(Y)也能走回vertex(X)。因此,要找到strongly connected component需要更高級的方法才行。

不過到這裡,是時候該說再見了朋友們
更高級的方法,請待下回分曉。



參考資料:


BFS/DFS系列文章

Graph: Breadth-First Search(BFS,廣度優先搜尋)
Graph: Depth-First Search(DFS,深度優先搜尋)
Graph: 利用DFS和BFS尋找Connected Component
Grpah: 利用DFS尋找Strongly Connected Component(SCC)
Grpah: 利用DFS尋找DAG的Topological Sort(拓撲排序)

回到目錄:

目錄:演算法與資料結構


tags: C++, Graph, BFS, DFS,