拓撲排序原理與解題套路 | 算法必看知識十九

原文連結

什麼是拓撲排序

其實最開始學習算法，聽到拓撲排序這幾個字我也是懵逼的，後來學着學着才慢慢知道是怎麼一回事。關于 拓撲 這個詞，在網上找到這麼一段解釋：

所謂“拓撲”就是把實體抽象成與其大小、形狀無關的“點”，而把連接配接實體的線路抽象成“線”，進而以圖的形式來表示這些點與線之間關系的方法，其目的在于研究這些點、線之間的相連關系。

表示點和線之間關系的圖被稱為拓撲結構圖。

拓撲結構與幾何結構屬于兩個不同的數學概念。

在幾何結構中，我們要考察的是點、線之間的位置關系，或者說幾何結構強調的是點與線所構成的形狀及大小。如梯形、正方形、平行四邊形及圓都屬于不同的幾何結構，但從拓撲結構的角度去看，由于點、線間的連接配接關系相同，進而具有相同的拓撲結構即環型結構。

也就是說，不同的幾何結構可能具有相同的拓撲結構。

拓撲在計算機領域研究的就是圖，既然是圖，那就會有節點和邊，節點表示的是現實生活中抽象的東西，邊表示的是這些東西之間的關系。

仔細想想，其實作實生活中的很多東西都能夠抽象成計算機世界當中的圖。

比如說對于實際的地圖，我們可以用節點表示岔路口，邊表示岔路口之間的連線；人的朋友圈，我們用節點表示人，用邊表示人與人之間的關系；再比如曆史事件，我們用節點表示事件，用邊表示事件之間的聯系；不管是人或者事，隻要找到了其對應的聯系，往往都可以抽象成圖。

拓撲排序解決的是依賴圖問題。

依賴圖表示的是節點的關系是有依賴性的，比如你要做事件 A，前提是你已經做了事件 B。除了 “先有雞還是先有蛋” 這類問題，一般來說事件的依賴關系是單向的，是以我們都用 有向無環圖 來表示依賴關系。

拓撲排序就是根據這些依賴來給出一個做事情，或者是事件的一個順序。

舉個例子，朋友來家裡吃飯，你準備做飯，你要做飯，首先得買菜，買菜得去超市，去超市要出門搭車，是以這個順序就是 出門搭車 -> 到超市 -> 買菜 -> 回家做飯。

當然我舉的這個例子你不需要計算機的幫助也能很清楚地知道這個順序，但是有些事情并不好直接看出來，比如常見的 “一個非常大的項目中，如何确定源代碼檔案的依賴關系，并給出相應的編譯順序？”。

我們要學的是一個解決一類問題的普适的方法，而不是學習怎麼快速得到一個具體問題的結果，換句話說，在學習之中，思考過程往往比結果和答案更重要。

實作原理

和圖相關的問題常見的算法就是搜尋，深度和廣度，拓撲排序也不例外，我們首先來看看稍微簡單，好了解的廣度優先搜尋，先放上代碼模版：

public List<...> bfsTopologicalSort() {
    // 邊界條件檢測
    if (...) {
        return true;
    }
    Map<..., List<...>> graph = new HashMap<>();
    // 建構圖
    ...
    // 這裡表示的是對于每個節點，其有多少前置條件（前置節點）
    int[] inDegree = new int[totalNodeNumber];

    // 根據圖中節點的依賴關系去改變 inDegree 數組
    for (Entry.Map<..., List<...>> entry : graph.entrySet()) {
        ...
    }

    Queue<...> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; ++i) {
        if (inDegree[i] == 0) {
            queue.offer(...);
        } 
    }

    List<...> result = new ArrayList<...>();
    while (!queue.isEmpty()) {
        int cur = queue.poll();

        // 記錄目前結果
        result.add(...);

        // 對于目前節點，解除對其下一層節點的限制
        for (... i : map.getOrDefault(cur, new ArrayList<...>())) {
            inDegree[i]--;
            if (inDegree[i] == 0) {
                queue.offer(...);
            }
        }
    }

    return result;
}           

拓撲排序問題是基于圖的算法，那麼首先我們要做的就是将問題抽象為圖。

這裡我用了一個 HashMap 來表示圖，其中 Key 表示的是具體的一個節點，Value 表示的是這個節點其下層節點，也就是 List 裡面的節點依賴于目前節點，之是以這樣表示依賴關系是為了我們後面實作的友善。

接下來我們會用一個 inDegree 數組來表示每個節點有多少個依賴的節點，選出那些不依賴任何節點的節點，這些節點應該被最先輸出，按照一般的廣度優先搜尋思維，我們開一個隊列，将這些沒有依賴的節點放進去。

最後就是廣度優先搜尋的步驟，我們保證從隊列裡面出來的節點是目前沒有依賴或者依賴已經被解除的節點，我們将這些節點輸出，這個節點輸出，其下一層節點的依賴就要相應的減少，我們改變 inDegree 數組中對應的值即可，如果改變後，對應節點沒有任何依賴了，表明這個節點可以被輸出了，就把它加進隊列，等待被輸出。

最後的最後就是輸出我們得到的答案，但是這裡要提醒的是，我們要考慮出現環的情況，就類似 “雞生蛋，蛋生雞” 的問題，比如 A 依賴于 B，B 也依賴于 A，這時我們是得不到答案的。

我們再來看看深度優先搜尋，其思想和前面講的廣度優先搜尋略微不同，我們不再需要 inDegree 數組了，而且我們需要去用另一種方式去判斷圖中是否存在環，先放上代碼模版：

public ... dfsTopologicalSort() {
    // 邊界條件檢測
    if (...) {

    }

    Map<..., List<...>> graph = new HashMap<>();

    // 建構圖
    ...

    boolean[] visited = new boolean[numCourses];
    boolean[] isLooped = new boolean[numCourses];

    List<...> result = new ArrayList<...>();
    for (int i = 0; i < totalNodeNumber; ++i) {                       
        if (!visited[i] && !dfs(result, graph, visited, isLooped, i)) {
            return new ArrayList<...>();
        }
    }

    return result;
}

private ... dfs(List<...> result,
                Map<..., List<...>>[] graph,
                boolean[] visited,
                boolean[] isLoop,
                ... curNode) {
    // 判斷是否有環
    if (isLoop[curNode]) {
        return false;
    }

    isLoop[curNode] = true;

    // 周遊目前節點的前置節點，也就是依賴節點
    for (int i : graph.get(curNode) {
        if (visited[i]) {
            continue;
        }

        if (!dfs(graph, visited, isLoop, i)) {
            return false;
        }
    }

    isLoop[curNode] = false;

    // record answer
    result.add(curNode)
    visited[curNode] = true;

    return true;
}           

有一點需要注意的是，建構圖的時候，我們需要和之前的廣度優先搜尋反轉一下，也就是這裡的 Key 表示的是一個節點，Value 中存的是其所依賴的節點，這也是和我們的實作方式有關，我們需要用到遞歸，遞歸用到函數棧，先處理的函數（節點）後輸出結果。

了解了上面這一點，下面就是用遞歸去解決這個深度優先搜尋問題，但是有一點是我們需要用到兩個 boolean 數組，一個（visited 數組）是記錄我們通路過的節點，避免重複通路，另外一個是防止環的出現，怎麼避免，深度優先搜尋是沿着一條路徑一直搜尋下去，我們需要保證這一條路徑不會經過某個節點兩次，注意我這裡說的是一條路徑。

兩種算法算是兩種實作的方式，但是目的都是一樣的，思想是類似的。

拓撲排序其實就是圖類問題當中的一個簡單應用，它其實是有固定的實作方式的，我們隻需要掌握這些實作方式中的算法思想，相信它不再是一個難題。

我們做題不是為了訓練我們的做題速度，編碼能力，更重要的是學習算法裡面的一種思考問題的方式和方法，這種先進的思想或者說是思維模式可以引領着我們朝計算機領域更廣闊、更深層次的地方去。

--- END ---

作者 | P.yh

來源 | 五分鐘學算法