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,