Leetcode 刷題 pattern - Topological Sort


Posted by Po-Jen on 2020-05-10

前言

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

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

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

Topological Sort 簡介

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

例如你睡前要做幾件事:

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

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

img

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

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

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

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

順序上就是:

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

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

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

題目

img

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 演算法工程師,希望活在當下,看到本質


#Leetcode









Related Posts

4. 安裝與使用第三方套件

4. 安裝與使用第三方套件

人性較量Day06~量化資訊

人性較量Day06~量化資訊

[新手村系列] Python 101 快速入門教學

[新手村系列] Python 101 快速入門教學



Newsletter




Comments