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

Attention is all you need.

Attention is all you need.

輸入資料 是否為自然數的 判斷演算法

輸入資料 是否為自然數的 判斷演算法

Remove Duplicates from an Array (ES6)

Remove Duplicates from an Array (ES6)




Newsletter




Comments