【圖論】有向無環圖的拓撲排序

1. 引言

有向無環圖（Directed Acyclic Graph, DAG）是有向圖的一種，字面意思的理解就是圖中沒有環。常常被用來表示事件之間的驅動依賴關系，管理任務之間的調度。拓撲排序是對DAG的頂點進行排序，使得對每一條有向邊(u, v)，均有u（在排序記錄中）比v先出現。亦可理解為對某點v而言，只有當v的所有源點均出現了，v才能出現。

下圖給出有向無環圖的拓撲排序：

下圖給出的頂點排序不是拓撲排序，因為頂點D的鄰接點E比其先出現：

2. 算法原理與實現

下面給出拓撲排序的兩種實現算法，其時間復雜度相等。

入度表

對於DAG的拓撲排序，顯而易見的辦法：

• 找出圖中0入度的頂點；
• 依次在圖中刪除這些頂點，刪除後再找出0入度的頂點；
• 然後再刪除……再找出……
• 直至刪除所有頂點，即完成拓撲排序

為了保存0入度的頂點，我們采用數據結構棧（亦可用隊列）；算法的可視化可參看這裡。

圖用鄰接表（adjacency list）表示，用數組inDegreeArray[]記錄節點的入度變化情況。C實現：

// get in-degree array
int *getInDegree(Graph *g) {
    int *inDegreeArray = (int *) malloc(g->V * sizeof(int));
    memset(inDegreeArray, 0, g->V * sizeof(int));
    int i;
    AdjListNode *pCrawl;
    for(i = 0; i < g->V; i++) {
        pCrawl = g->array[i].head;
        while(pCrawl) {
            inDegreeArray[pCrawl->dest]++;
            pCrawl = pCrawl->next;
        }
    }
    return inDegreeArray;
}

// topological sort function
void topologicalSort(Graph *g) {
    int *inDegreeArray = getInDegree(g);
    Stack *zeroInDegree = initStack();
    int i;
    for(i = 0; i < g->V; i++) {
        if(inDegreeArray[i] == 0)
            push(i, zeroInDegree);
    }

    printf("topological sorted order\n");
    AdjListNode *pCrawl;
    while(!isEmpty(zeroInDegree)) {
        i = pop(zeroInDegree);
        printf("vertex %d\n", i);

        pCrawl = g->array[i].head;
        while(pCrawl) {
            inDegreeArray[pCrawl->dest]--;
            if(inDegreeArray[pCrawl->dest] == 0)
                push(pCrawl->dest, zeroInDegree);
            pCrawl = pCrawl->next;
        }
    }
}

時間復雜度：得到inDegreeArray[]數組的復雜度為O(V+E)  ；頂點進棧出棧，其復雜度為O(V)  ；刪除頂點後將鄰接點的入度減1，其復雜度為O(E)  ；整個算法的復雜度為O(V+E)  。

DFS

在DFS中，依次打印所遍歷到的頂點；而在拓撲排序時，頂點必須比其鄰接點先出現。在下圖中，頂點5比頂點0先出現，頂點4比頂點1先出現。

在DFS實現拓撲排序時，用棧來保存拓撲排序的頂點序列；並且保證在某頂點入棧前，其所有鄰接點已入棧。DFS版拓撲排序的可視化參看這裡。

C實現：

/* recursive DFS function to traverse the graph,* the graph is represented by adjacency list*/
void dfs(int u, Graph *g, int *visit, Stack *s) {
   visit[u] = 1;
   AdjListNode *pCrawl = g->array[u].head;
   while(pCrawl) {
       if(!visit[pCrawl->dest])
           dfs(pCrawl->dest, g, visit, s);
       pCrawl = pCrawl->next;
   }
   push(u, s);
}

// the topological sort function
void topologicalSort(Graph *g) {
   int *visit = (int *) malloc(g->V * sizeof(int));
   memset(visit, 0, g->V * sizeof(int));
   Stack *s = initStack();
   int i;
   for(i = 0; i < g->V; i++) {
       if(!visit[i]) dfs(i, g, visit, s);
   }

   // the order of stack element is the sorted order
   while(!isEmpty(s)) {
       printf("vertex %d\n", pop(s));
   }
}

時間復雜度：應與DFS相同，為O(V+E)  。

完整代碼在Github。

3. 參考資料

[1] R. Rao, Lecture 20: Topo-Sort and Dijkstra’s Greedy Idea.
[2] GeeksforGeeks, Topological Sorting.
[3] GeeksforGeeks, Graph and its representations.