[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)

V 表示點頂數, E 表示 edge 邊數

網頁瀏覽量: 0


尚未有留言,成為第一個留言的人吧!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *