Leetcode 刷題 pattern - Topological Sort

前言

身在大 CS 時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項 和 當我們在學程式時，要學的到底是什麼？ 講得很好，寫題目是為了學會解題的思考法，確保自己掌握重要的資料結構跟演算法。這也是我寫這系列文章的原因，我想把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。

另外，這系列文章提供的做法雖然可以讓面試準備事半功倍，但不一定適合你。如果你比較喜歡透過刷很多題來鍛鍊演算法跟資料結構的直覺，那你可以參考 這篇短文，踏上刷遍一千題、融會貫通 computational thinking。

接著就讓我們進入今天的主題 - Topological Sort。

Topological Sort 簡介

Topological Sort 是一個很特別的 pattern，可以在具有 "前後依賴關係" 的 graph 中找出合理的順序。

例如你睡前要做幾件事：

1. 刷牙
2. 洗臉
3. 吃早餐
4. 穿襪子
5. 穿鞋子
6. 換衣服

其中某些事情有先後依賴關係，例如你要先穿襪子，然後才穿鞋子，概念上就像下圖：

如果你今天只有這些依賴關係：

刷牙 -> 吃早餐
換衣服 -> 穿襪子
洗臉 -> 吃早餐
穿襪子 -> 穿鞋子
吃早餐 -> 換衣服

你要怎麼寫程式來得到正確的執行順序呢？這就是 topological sort 要做到的事情。

而要找出正確的執行順序，概念上也很簡單。我們可以先找出不依賴其他事情的事項 - "刷牙" & "洗臉"，從這些事項開始，做完之後就從圖上移掉，然後再從下一個不依賴其他事情的事項開始，直到所有事情都做完或發現有互相依賴導致做不完。

順序上就是：

1. 找出刷牙、洗臉都不依賴於其他事情
2. 刷牙、洗臉
3. 把刷牙跟洗臉從待辦事項移除
4. 找出吃早餐不依賴於其他事情
5. 吃早餐
6. ...

直到所有事情都做完。至於要怎麼實作這個直觀的想法，我們直接透過第一個範例來學習吧。

Topological Sort 的第一個範例 - Leetcode #207 - Course Schedule

題目

Topological Sort 解法

Graph 有兩種常見的儲存方法 - Adjacency Matrix 跟 Adjacency list，這邊我們可以用 adjacency list 來表示 graph，也就是儲存每個 node 跟這個 node 的 list of children，以題目中的第一個範例來說，就是：

node 0: [1]
node 1: []

另外為了方便找出哪些 node ，可以再儲存一個 inDegree 來表示有多少個 edge 指向這個 node。所以只要某個 node 的 inDegree 是 0，那就表示這個 node 不依賴其他 node，所以可以準備來移除這個 node。

每次我們只要找到 inDegree 是 0 的 node（也就是 source），就把這個 node 放到 source，並更新這個 node 所有 child 的 inDegree，直到 source 再也沒有其他的 node。

概念上滿簡單的，實作起來需要習慣一下，可以參考下面的 C++ 實作：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // Init the graph
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> graph;
        for(int i = 0; i < numCourses; ++i) {
            inDegree[i] = 0;
            graph[i] = {};
        }

        // Build the graph
        for(int i = 0; i < prerequisites.size(); ++i) {
            int prereq = prerequisites[i][1];
            int course = prerequisites[i][0];

            graph[prereq].push_back(course);
            ++inDegree[course];
        }

        // Find all sources
        queue<int> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            }
        }

        // Build the sorted order
        vector<int> sortedCourse;
        while(!sources.empty()) {
            int course = sources.front();
            sources.pop();

            sortedCourse.push_back(course);

            for(auto& child: graph[course]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        // If the size of topological order list is not equal to numCourses
        // Return false
        return sortedCourse.size() == numCourses;
    }
};

210. Course Schedule II 跟這題基本上寫法是一模一樣的，只差在回傳的東西不同，你可以自己寫寫看 210 ，檢驗一下自己是否有弄懂 207 的所有細節。

Topological Sort 的第二個範例 - Leetcode #269 - Alien Dictionary

題目

Topological Sort 解法

這題之所以適合拿來當作第二個範例，是因為除了 build graph 的地方不同，其他的邏輯幾乎是一模一樣。至於要怎麼 build graph，其實也只是要在給定的 dictionary 中找出 prerequisite 的關係而已，而這個 prerequsite 關係只有在兩個 word 之間比較才有意義，例如：

wrt
wrf

包含的訊息只有 t 要在 f 前面，至於 w, r, t 之間是什麼關係，我們無法從上例中看出，因為一個 word 裡面 character 的不需排序。

根據新的 build graph 方法，只需要稍微修改上題的解法，就可以寫出下面的程式碼：

class Solution {
public:
    string alienOrder(vector<string>& words) {
        // Init the graph
        unordered_map<char, int> inDegree;
        unordered_map<char, vector<char>> graph;
        for (auto word : words) {
            for (char character : word) {
                inDegree[character] = 0;
                graph[character] = vector<char>();
            }
        }

        // Build the graph
        for (int i = 0; i < words.size() - 1; i++) {
            // find ordering of characters from adjacent words
            string w1 = words[i], w2 = words[i + 1]; 

            for (int j = 0; j < min(w1.length(), w2.length()); j++) {
                char parent = w1[j], child = w2[j];
                if (parent != child) {             // if the two characters are different
                    graph[parent].push_back(child);  // put the child into it's parent's list   
                    inDegree[child]++;               // increment child's inDegree
                    break;  // only the first different character between the two words will help us 
                }
            }
        }

        // Find sources
        queue<char> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            }
        }

        // Start toppological sort
        string order;
        while(!sources.empty()) {
            char cur = sources.front();
            sources.pop();

            order += cur;

            for(auto& child: graph[cur]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        return order.length() == inDegree.size() ? order : "";
    }
};

Topological Sort 的第三個範例 - Leetcode #444 - Sequence Reconstruction

題目

Topological Sort 解法

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        // Init the graph
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> graph;
        for(auto& seq: seqs) {
            for(auto& num: seq) {
                inDegree[num] = 0;
                graph[num] = {};
            }
        }

        // Build the graph
        for(auto& seq: seqs) {
            if(seq.empty()) {
                continue;
            }

            for(int i = 0; i < seq.size() - 1; ++i) {
                int parent = seq[i];
                int child = seq[i + 1];
                ++inDegree[child];
                graph[parent].push_back(child);
            }
        }

        // If inDegree's size != org.size, that means there's not enough information        
        if(inDegree.size() != org.size()) {
            return false;
        }

        // Find sources
        queue<int> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            } 
        }

        // Start topological sort
        // In each step, if source's size > 1 or sources.front() does not match org, it's wrong
        vector<int> order;
        while(!sources.empty()) {
            // If there are more than one choice at this time
            if(sources.size() > 1) {
                return false;
            }

            if(org[order.size()] != sources.front()) {
                return false;
            }

            int cur = sources.front();
            sources.pop();

            order.push_back(cur);

            for(auto& child: graph[cur]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        return order.size() == org.size();
    }
};

總結

今天跟大家介紹了一個新的 pattern - Topological Sort，順便提供幾個經典的可應用題，讓大家體驗一下用這個 pattern 的好處。希望大家在刷題的時候也能多掌握解題的 pattern，用一個 pattern 打掉多題，體會到隱藏在這些 pattern 後的演算法和資料結構的優美之處。

延伸閱讀

1. Leetcode 刷題 pattern - Two Pointer
2. Leetcode 刷題 pattern - Sliding Window
3. Leetcode 刷題 pattern - Next Greater Element
4. Leetcode 刷題 pattern - Fast & Slow Pointer
5. Leetcode 刷題 pattern - Breadth-First Search
6. Leetcode 刷題 pattern - Merge Intervals
7. Leetcode 刷題 pattern - Cyclic Sort
8. Leetcode 刷題 pattern - Two Heaps
9. Leetcode 刷題 pattern - Top K elements

關於作者：
@pojenlai 演算法工程師，希望活在當下，看到本質。