前言
身在大 CS 時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項 和 當我們在學程式時，要學的到底是什麼？ 講得很好，寫題目是為了學會解題的思考法，確保自己掌握重要的資料結構跟演算法。這也是我寫這系列文章的原因，我想把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。
另外，這系列文章提供的做法雖然可以讓面試準備事半功倍，但不一定適合你。如果你比較喜歡透過刷很多題來鍛鍊演算法跟資料結構的直覺，那你可以參考 這篇短文，踏上刷遍一千題、融會貫通 computational thinking。
接著就讓我們進入今天的主題 - Topological Sort。
Topological Sort 簡介
Topological Sort 是一個很特別的 pattern，可以在具有 "前後依賴關係" 的 graph 中找出合理的順序。
例如你睡前要做幾件事：
- 刷牙
- 洗臉
- 吃早餐
- 穿襪子
- 穿鞋子
- 換衣服
其中某些事情有先後依賴關係，例如你要先穿襪子，然後才穿鞋子，概念上就像下圖：
如果你今天只有這些依賴關係：
刷牙 -> 吃早餐
換衣服 -> 穿襪子
洗臉 -> 吃早餐
穿襪子 -> 穿鞋子
吃早餐 -> 換衣服
你要怎麼寫程式來得到正確的執行順序呢？這就是 topological sort 要做到的事情。
而要找出正確的執行順序，概念上也很簡單。我們可以先找出不依賴其他事情的事項 - "刷牙" & "洗臉"，從這些事項開始，做完之後就從圖上移掉，然後再從下一個不依賴其他事情的事項開始，直到所有事情都做完或發現有互相依賴導致做不完。
順序上就是：
- 找出刷牙、洗臉都不依賴於其他事情
- 刷牙、洗臉
- 把刷牙跟洗臉從待辦事項移除
- 找出吃早餐不依賴於其他事情
- 吃早餐
- ...
直到所有事情都做完。至於要怎麼實作這個直觀的想法，我們直接透過第一個範例來學習吧。
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 後的演算法和資料結構的優美之處。
延伸閱讀
- Leetcode 刷題 pattern - Two Pointer
- Leetcode 刷題 pattern - Sliding Window
- Leetcode 刷題 pattern - Next Greater Element
- Leetcode 刷題 pattern - Fast & Slow Pointer
- Leetcode 刷題 pattern - Breadth-First Search
- Leetcode 刷題 pattern - Merge Intervals
- Leetcode 刷題 pattern - Cyclic Sort
- Leetcode 刷題 pattern - Two Heaps
- Leetcode 刷題 pattern - Top K elements
 - Service_@AlanSyue_https://static.coderbridge.com/img/AlanSyue/c1a8c2055ceb4302976788ea97bd060f.png)
