圖解:什麼是拓撲排序?

今天景禹給你們談一談拓撲排序，乍一聽上去，感覺很高大上，但她的確很高大上，所以一起徵服她吧！在正式介紹拓撲排序之前，我們一起看一看必備基礎。拓撲排序基礎篇 總覺得書上的概念有點欠缺生動，但還是需要這些基礎的概念作為支撐。一個 無環的有向圖 稱為 有向無環圖（Directed Acycline Graph），簡稱 DAG 圖。（這不等於沒說嗎？）所以直接看圖。圖中最左邊的是有向樹，中間的是有向無環圖，最右則的是有向圖（因為圖中BED三個頂點之間構成一個有向環，ACEB也存在環路）。所有的工程或者某種流程都可以分為若干個小的工程或者階段，我們稱這些小的工程或階段為「活動」。打個比方，如何把一隻大象裝到冰箱裡，很簡單，分三步。第一，打開冰箱門；第二，將大象裝進去；第三，關上冰箱門。這三步中的每一步便是一個 「活動」 。在一個表示工程的有向圖中，用 頂點表示活動，用弧表示活動之間的優先關係的有向圖 稱為頂點表示活動的網（Activity On Vertex Network），簡稱AOV網。AOV網中的弧表示活動之間存在的某種制約關係，比如上面說到將大象裝入冰箱，必須先打開冰箱門，才能將大象裝進去，大象裝進去才能關上冰箱門，從而完成我們的任務。還有一個經典的例子那就是選課，通常我們是學了C語言程序設計，才能學習數據結構，這裡的制約關係就是課程之間的優先關係。（之後我們會講一個完整的例子，大家就會更清楚AOV網）設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列 一個拓撲序列 ，整個過程便叫做 拓撲排序。有向有環圖其實過程和之前類似，只是給大家提供一個思路，如果面試官問你，如何判斷一個有向圖中是否存在環時，你應該第一反應想到的就是拓撲排序，為什麼拓撲排序可以判斷一個有向圖中是否存在環呢？我們看慄子。第一步：在有向圖中選擇一個沒有前驅的頂點並輸出；圖中沒有前驅的頂點為A。第三步：在有向圖中選擇一個沒有前驅的頂點並輸出；圖中沒有前驅的頂點為C。第五步：在有向圖中選擇一個沒有前驅的頂點並輸出；發現當前圖不存在無前驅的頂點，但拓撲序列中並未輸出所有的頂點，所以剩下的頂點構成了環，也證明了該有向圖存在環。拓撲排序實現篇 針對於拓撲排序思想篇提到的兩步操作，我們採用鄰接表作為有向圖的存儲結構，並且在頭結點中增加一個存放頂點入度的數組（indegree）。入度為零的頂點即為沒有前驅的頂點，刪除頂點及以它為尾的弧的操作，則則可換以弧頭頂點的入度減1來實現。為了避免重複檢查入度為零的頂點，可另設一個棧暫存所有入度為領的頂點。為了清晰地呈現拓撲排序的實現，我們還是以上面提到的有向無環圖為慄子進行講解，Step By Step。第一步：遍歷所有頂點，將入度為0的頂點入棧，即分別將頂點

// 拓撲排序算法
// 若GL無迴路，則輸出拓撲排序序列並返回OK，否則返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
   EdgeNode *e;
   int i, k, gettop;
   int top = 0;  // 用於棧指針下標索引
   int count = 0;  // 用於統計輸出頂點的個數
   int *stack;   // 用於存儲入度為0的頂點
 
   stack = (int *)malloc(GL->numVertexes * sizeof(int));
 
   for( i=0; i < GL->numVertexes; i++ )
   {
      if( 0 == GL->adjList[i].in )
      {
         stack[++top] = i; // 將度為0的頂點下標入棧
      }
   }
 
   while( 0 != top )
   {
      gettop = stack[top--]; // 出棧
      printf("%d -> ", GL->adjList[gettop].data);
      count++;    
  
      for( e=GL->adjList[gettop].firstedge; e; e=e->next )
      {
         k = e->adjvex;
   // 注意：下邊這個if條件是分析整個程序的要點！
   // 將k號頂點鄰接點的入度-1，因為他的前驅已經消除
   // 接著判斷-1後入度是否為0，如果為0則也入棧
         if( !(--GL->adjList[k].in) ) 
         {
            stack[++top] = k;
         }
      }
   }
 
   if( count < GL->numVertexes ) // 如果count小於頂點數，說明存在環
   {
      return ERROR;
   }
   else
   {
      return OK;
   }
}
時間複雜度分析對於包含n個頂點和 e 條弧的有向圖而言，求各個頂點的入度的時間複雜度為 請你判斷是否可能完成所有課程的學習？  你的第一反應是否想到題目就相當於判斷一個有向圖中是否有環呢？我相信小禹禹一定想到了，比如示例二的輸入就表示有向圖中存在環，所以不能完成所有課程，如下圖形式：而示例一中就不存在環，即可以完成所有課程，如下圖所示：當然真實的輸入可能比給的示例複雜的多，但是不論多麼複雜，只需要使用拓撲排序排查一遍即可，這就是算法的魅力。實現起來也很簡單，大家可以將上面的C語言代碼稍加改動即可，這裡景禹給大家提供利用棧實現的Java代碼：
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());

        for(int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }

        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) stack.add(i);

        while(!stack.isEmpty()) {
            int pre = stack.pollLast();
            numCourses--;
            for(int cur : adjacency.get(pre))
                if(--indegrees[cur] == 0) stack.add(cur);
        }
        return numCourses == 0;
    }
}
還有一道題目，LeetCode 210. 課程表 II (course-schedule))，有興趣的小禹禹可以去試一試，其實只要在 207 的解法上增加一個輸出即可，景禹就不在這裡廢話了，但是景禹要給大家提供一種輸出所有拓撲序列的代碼，可供學有餘力的小禹禹抽空自己調試運行理解。
import java.util.*; 

class Graph { 
    int V; 

    List<Integer> adjListArray[]; 

    public Graph(int V) { 

    this.V = V; 

    @SuppressWarnings("unchecked") 
    List<Integer> adjListArray[] = new LinkedList[V]; 

    this.adjListArray = adjListArray; 

    for (int i = 0; i < V; i++) { 
       adjListArray[i] = new LinkedList<>(); 
    } 
 } 

 public void addEdge(int src, int dest) { 

    this.adjListArray[src].add(dest); 

 } 
 

private void allTopologicalSortsUtil(boolean[] visited, 
    int[] indegree, ArrayList<Integer> stack) { 
    boolean flag = false; 

    for (int i = 0; i < this.V; i++) { 
       if (!visited[i] && indegree[i] == 0) { 
        visited[i] = true; 
        stack.add(i); 
        for (int adjacent : this.adjListArray[i]) { 
       indegree[adjacent]--; 
    } 
    allTopologicalSortsUtil(visited, indegree, stack); 
    
    visited[i] = false; 
    stack.remove(stack.size() - 1); 
    for (int adjacent : this.adjListArray[i]) { 
       indegree[adjacent]++; 
    } 
    flag = true; 
    } 
  } 

    if (!flag) { 
       stack.forEach(i -> System.out.print(i + " ")); 
       System.out.println(); 
    } 
 } 
 

public void allTopologicalSorts() { 
    boolean[] visited = new boolean[this.V]; 

    int[] indegree = new int[this.V]; 

    for (int i = 0; i < this.V; i++) { 
       for (int var : this.adjListArray[i]) { 
          indegree[var]++; 
       } 
    } 

    ArrayList<Integer> stack = new ArrayList<>(); 

    allTopologicalSortsUtil(visited, indegree, stack); 
 } 
 

 public static void main(String[] args) { 

    Graph graph = new Graph(6); 
    graph.addEdge(5, 2); 
    graph.addEdge(5, 0); 
    graph.addEdge(4, 0); 
    graph.addEdge(4, 1); 
    graph.addEdge(2, 3); 
    graph.addEdge(3, 1); 

    System.out.println("All Topological sorts"); 
    graph.allTopologicalSorts(); 
 } 
} 
總結 拓撲排序在實際的生產中很常見，最經典的例子就是課程表，當然還可以進行代碼的依賴關係處理等等，此外，拓撲排序還是之後要將的關鍵路徑的基礎，所以希望各位小禹禹好好學習，有所進步。