必須是一個有向無環圖 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