聊聊拓撲排序算法

起因

最近在項目上實現功能時，遇到了一個需求，需要把一個 excel 里的數據按照一定規則轉換成 sql，用的實現方法與之前一篇博客 Attribute + TypeConverter 實現 Excel To Json 中的思想類似，使用 attribute (java 里叫 annotation) 來在 model 上標記 property 與 excel 列名的對應關係，但是在分析 excel 時遇到了更複雜的情況，某一列的驗證規則需要基於其他列的值，因此在轉換列值的時候需要考慮列與列之間的依賴關係，被依賴的列需要先轉換。這就需要一種算法來對列的轉換順序進行排序，把被依賴的列放在轉換序列的前面，把有依賴的列放在轉換序列的後面，這樣只要按照這個轉換序列來依次轉換所有的列，就不會有問題了，舉個例子，假如我的 excel 里有 A B C D 4列，其中 A 列的值在驗證時需要 判斷 D 列的值，假設 D 的值為 true，需要 A 的值為 1， 假設 D 的值為 false，需要 A 的值為 2，也就是說 A 的值需要 D 的值為前提條件進行判斷，所以在轉換的時候我們需要先轉換 D 後轉換 A，因此理想的轉換序列應該是 D A B C

從另一個角度說，我們也需要一個算法來檢查我的 attribute 里是否出現了由於錯誤引起的循環依賴問題。還是上面的例子，假如 A 依賴 D 的值， D 依賴 C 的值，C 依賴 A 的值，就形成了一個循環依賴

C -> D -> A -> C

這種情況下是無法進行解析的，應該檢查是否有邏輯錯誤。

在網上搜索時發現 拓撲排序算法 剛好就是用來分析各個任務之間的依賴關係，並且能過分析出各個任務之間有沒有循環引用的情況，下面來聊聊拓撲排序算法

什麼是拓撲排序

拓撲排序(Topological Sorting)是一種把有向無環圖(DAG, Directed Acyclic Graph)轉換成線性序列的排序算法，算法的輸入是一個 有向無環圖 ，經過算法分析把圖中的所有節點按照先後順序(依賴關係)進行拆解，最後得到一個有順序的隊列，在前(被依賴)的節點靠前，越靠後的節點或有多個節點指向該節點，那這個節點在隊列中的位置就越靠後。

看下面這個例子

節點 5 和 4 不依賴任何節點，因此在輸出隊列里也靠前，而 0 和 1 分別有 2 個依賴的節點，因此需要靠後處理，經過拓撲排序後的結果：

5 4 2 3 1 0

需要注意的是拓撲排序的結果可能不唯一，起點通常是一個入度為 0 的節點

下面兩種排序結果都是正確的：

5 4 2 3 1 0

4 5 2 3 0 1

入度

這裡出現了一個新的概念– 入度 ，入度指的是以該節點為 終點 的邊的數量

上圖的 0 和 1 節點 的入度為 2，5 和 4 的入度為 0，2 和 3 的入度為 1

有向無環圖

引自維基百科，在圖論中，如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖（DAG,directed acyclic graph）

有向指的是節點之間的邊是有方向的，從一個節點到另一個節點，例如 A -> B ，我們可以理解為 B 對 A有依賴，要完成 B 需要先完成 A。

無環指的是不存在從一個節點出發，最終又回到當前節點的路徑。

回到上面的例子，

C -> D -> A -> C

從 C 出發最後又回到了 C，就形成了一個環，代表出現了循環依賴

算法思路

我們可以把排序的過程看做是解依賴的過程，

1. 把所有沒有依賴的節點（入度為 0）放進一個隊列
2. 從隊列拿出一個節點，從圖中拿掉這個節點（相當於這個任務完成了），同時拿掉它指向別的節點的邊，把它指向的節點的入度減 1，如果它指向的節點 入度變為 0（沒有依賴了），則把該節點放入隊列
3. 重複第 2 步，直到所有的節點都從圖上拿走
4. 把節點從圖上拿走的順序，就是最終輸出的序列

用一張圖來表示這個過程，圖中的紅色數字表示 入度

1. 找到入度為 0 的節點 1
2. 拿掉 節點 1，此時 節點 2 的入度變為 0，4 的入度變成 1
3. 拿掉 節點 2，節點 3 的入度變為 1， 節點 4 的入度為 0
4. 拿掉 節點 4，節點 3 的入度為 0，節點 5 的入度為 1
5. 拿掉 節點 3，節點 5 的入度為 0
6. 拿掉 節點 5，結束

最後的輸出順序：

1 2 4 3 5

判斷環

如果有環存在，則在不斷拿掉點的過程中，出現圖上還有節點，但是無法找到入度為 0 的點， 看下面這個圖

圖中 B-C—E 是一個環，我們看看當只剩 B-C—E 3 個節點時各個節點的入度情況

根據拓撲排序算法，需要找到當前圖中所有入度為 0 的節點，依次放入隊列並去掉這個節點，把它的邊指向的節點入度減 1，但此時 B C E 的入度都為 1，不存在入度為 0 的點，因此算法無法進行下去，所以我們只要判斷當入度為 0 的隊列為空之後，已經拿掉的節點的個數與原來的節點總個數是否相等，如果相等則表示全部處理完，如果不想等表示有圖存在，上圖的例子中，拿掉的節點數為 2 (AD)，此時圖上已經不存在入度為 0 的點，但是頂點總數為 5，與 2 不相等，因此說明圖中存在環

算法實現

class Graph {
 Map> referenceMap; //存放邊
 Queue nodeQueue; //用於放入度為 0 的節點
 Map nodeIndegreeMap; //存放節點和入度

 List topologicalSort() {
 List result = new ArrayList<>();
 for (String nodeName : nodeIndegreeMap.keySet()) {
 if (nodeIndegreeMap.get(nodeName) == 0) {
 nodeQueue.add(nodeName);
 }
 }

 int count = 0;
 while (!nodeQueue.isEmpty()) {
 String node = nodeQueue.poll();
 result.add(node);
 count++;
 for (String c : referenceMap.get(node)) {
 int indegree = nodeIndegreeMap.get(c) - 1;
 nodeIndegreeMap.replace(c, indegree);
 if (indegree == 0) {
 nodeQueue.add(c);
 }
 }
 }

 if (count < referenceMap.size()) {
 String restNodes = nodeIndegreeMap.keySet().stream().filter(k -> !result.contains(k))
 .collect(
 Collectors.joining(","));
 throw new IllegalArgumentException(
 "there are loop reference in the graph, check the config for nodes: "
 + restNodes);
 }

 return result;
 }
 }