Graph: 利用DFS尋找DAG的Topological Sort(拓撲排序)

Posted by Chiu CC on 2 18, 2016


先備知識與注意事項

有些事件具有絕對的「先後關係」,例如,襪子要在鞋子之前穿上,否則穿上鞋子後要再穿襪子需要一點奇蹟。

若以Graph來表示,vertex(穿襪子)、vertex(穿鞋子)與edge(先後關係)如圖一(a):

cc

圖一(a)。

Graph: Intro(簡介)曾經提過的「課程與其先修課程」亦具有這樣的「先後關係」。
例如,學生一定要先修過「資料結構」,才能選修「演算法分析」,否則選課系統會生氣。

那麼要如何確保在選修「演算法分析」之前,已經先選修「資料結構」,而在選修「資料結構」之前,已經先修完「程式(一)」與「離散數學」?

本篇文章將要介紹的Topological Sort(拓撲排序)就是要解決這項煩惱。
如果找到了圖一(b)的Topological Sort(拓撲排序),就能知道可行的修課順序,以確保在選修「演算法分析」之前,一定已經修過「資料結構」與「線性代數」。

cc

圖一(b)。


目錄


Topological Sort(拓撲排序)

所謂的Topological Sort(拓撲排序)要求,若directed acyclic graph(DAG)中存在一條edge(X,Y),那麼序列中,vertex(X)一定要在vertex(Y)之前出現。

  • 以圖二(a)為例,存在edge(2,6)、edge(6,9),那麼Topological Sort中,vertex(2)一定要出現在vertex(6)之前,vertex(6)一定要在vertex(9)之前。

cc

圖二(a):將圖一(b)以符號表示。

根據圖一(b),選修「資料結構」與「線性代數」的先後順序顯然無所謂,「數值分析」與「離散數學」的修課順序也互相沒有影響,因為兩者之間沒有必然的先後關係。
因此,正確的Topological Sort可能不止一種,以下兩種排序皆為圖二(a)的可能結果:

Topological Sort:
  3  4  5 14  1  0  2  7  6 12 13 11  9 10  8
Topological Sort:
  3  1  0  2  7  4  5 14  6 12 13 11  9 10  8

最重要的一點:只有directed acyclic graph(DAG)的Topological Sort(拓撲排序)才有意義。

  • 以圖二(b)為例,若根據Topological Sort的定義:「若存在一條edge(X,Y),則序列中,vertex(X)一定要在vertex(Y)之前出現」,那麼,存在edge(fish,rice),序列可能是「魚、飯、肉、菜」,但是卻也同時存在edge(rice,pork),序列可能是「飯、肉、菜、魚」,而第二個序列卻違反「存在edge(fish,rice),魚要在飯之前吃」的限制。
    因此,若directed graph中存在cycle,討論Topological Sort其實沒有什麼幫助。

cc

圖二(b)。


演算法

Graph: 利用DFS尋找Strongly Connected Component(SCC)曾經提過DAG的性質:

  • 在DAG上執行一次DFS(),若存在一條path從vertex(X)到vertex(Y),那麼finish[X]一定比finish[Y]還大。(證明請點這裡)

因此,只要進行一次DFS(),並且依照finish[]由大到小印出vertex,就是Topological Sort(拓撲排序)了。

cc

圖三。


程式碼

是的,只要把上一篇文章介紹過的PrintSCCs()的前半部照抄,就能夠找到finish由大到小的順序。

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

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *distance,
        *predecessor,
        *discover,
        *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];};
    int GetFinish(int i){return finish[i];};
    int GetPredecessor(int i){return predecessor[i];};

    void AddEdgeList(int from, int to);

    void BFS(int Start);
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);
    void VariableInitializeDFS();

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

    Graph GraphTranspose();
    void PrintSCCs(int Start = 0);

    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 TopologicalSort(int Start = 0);
};

void Graph::TopologicalSort(int Start){

    DFS(Start);         // 進行一次DFS用來取得 finish[]

    // 矩陣 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);

    std::cout << "Topological Sort:\n";
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(3) << finishLargetoSmall[i];
    std::cout << std::endl;
}

int main(){
    Graph g5(15);            // 建立如圖二(a)的DAG
    g5.AddEdgeList(0, 2);
    g5.AddEdgeList(1, 2);
    g5.AddEdgeList(2, 6);g5.AddEdgeList(2, 7);
    g5.AddEdgeList(3, 4);
    g5.AddEdgeList(4, 5);
    g5.AddEdgeList(5, 6);g5.AddEdgeList(5, 14);
    g5.AddEdgeList(6, 8);g5.AddEdgeList(6, 9);g5.AddEdgeList(6, 11);g5.AddEdgeList(6, 12);
    g5.AddEdgeList(7, 8);
    g5.AddEdgeList(9, 10);
    g5.AddEdgeList(12, 13);

    g5.TopologicalSort();
    g5.TopologicalSort(4);

    return 0;
}

output:

Topological Sort:
  3  4  5 14  1  0  2  7  6 12 13 11  9 10  8
Topological Sort:
  3  1  0  2  7  4  5 14  6 12 13 11  9 10  8


以上的做法是另外呼叫一個修改過的QuickSort(),對額外的矩陣finishLargetoSmall[]進行排序,優點是不需要更動DFS()

還有些常見的方法就是修改DFS(),主要有兩種,發生在當vertex要被標記為「已讀(visited)」或者「塗黑」時:

  1. 把剛剛塗黑的vertex放進stack中,那麼按照順序,最先被塗黑的vertex就最先被放入stack的vertex,也就最後被pop()stack
    因此,對stack依序進行pop()便能夠維持finish由大到小的順序。(詳見GeeksforGeeks:Topological Sorting)
  2. 或者,把剛剛塗黑的vertex推進(push)一串Linked list,那麼,只要每次都是在Linked list的前端(front)加入vertex,當有下一個vertex被推入Linked list時,先前finish較小的vertex就被往後挪。
    最後,對Linked list進行一次traversal,得到的vertex順序就會是finish由大到小。


以上便是利用DFS()來尋找DAG的Topological sort(拓撲排序)的介紹。
基本上是DFS()的變形/延伸,再一次finish又扮演關鍵角色拯救了世界。



參考資料:


BFS/DFS系列文章

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

回到目錄:

目錄:演算法與資料結構


tags: C++, Graph, DFS, DAG,