[Leetcode Pattern] 拓樸排序 Topological sort

必須是一個有向無環圖 DAG，才能有拓樸排序

套用時機

事件前後有依賴關係
判斷 graph 有無 Cycle

實例 – Leetcode 207. Course Schedule

題目：有不同課程需要相依性才能去上，例如 [0,1] 表示要先上過 1 才能上 0 的課程，問是否能找到一個順序上完呢？

思路：

假設以下的課程相依性，可以畫成一個 Graph

可以先轉換成 adjacency list

實作方式，使用Kahn 演算法：

可以看成使用 BFS

Step1. 從 Graph 裡選到 inDegree 為 0 的 vertex，輸出該 vertex

Step2. 從 Graph 中刪 vertex 及其所有的 edge (相鄰 vertex 的 inDegree 減去 1)

Step3. 時序執行 Step2. 直到所有 vertex 輸出，即拓墣排序完成，反之， Graph 中如果再沒有 inDegree 為 0 的 vertex 則代表此 Graph 有 cycle，無法達成拓墣排序

inDegree: 箭頭指到 vertex 的數目

▼ 然後按照上面提到的三個步驟 Kahn 演算法 依序處理

可以想成沒有被任何 edge 連到的 v 才能放到 queue 裡 (inDegree 數 == 0)

而當 queue.count 為 0 時，檢查是否一 traverse 過所有 v，如果沒有就帶表有 cycle 存在，無法完成拓樸排序

▼ 所以其中一種可能的拓樸排序如下

程式碼：

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        
        var graph = Array(repeating:[Int](),count:numCourses)
        var indegrees = Array(repeating:0,count:numCourses)
        
        for course in prerequisites {
            graph[course[1]].append(course[0])
            indegrees[course[0]] += 1
        }
        
        
        var queue = [Int]()
        for index in 0..<numCourses {
            if indegrees[index] == 0 {
                queue.insert(index, at: 0)
            }
        }
        print(queue)
        var count = numCourses
        while queue.count > 0 {
            let current = queue.removeLast()
        
            count -= 1
            for course in graph[current] {        
                indegrees[course] -= 1
                if indegrees[course] == 0 {
                    queue.insert(course, at: 0)
                }
            }
        }
        
        return count == 0 ? true : false
    }
}

時間複雜度：

因為 Graph 的資料結構是 adjacency list，所以時間複雜度是 O(V+E)