題目敘述
題目會給我們一個輸入陣列prerequisites，每個pair代表兩個課程之間的先修關係，和課程總數numCourses。
題目問我們這組課程表是否能依照順序修完所有的課程?
如果可以，返回True。如果不行，代表有擋修形成死結，無法依照順序修完所有的課程，返回False。
測試範例
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
0, 1兩個課程彼此擋修，形成互卡的死結，因此無法依照順序修完所有的課程。
約束條件
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi< numCourses- All the pairs prerequisites[i] are unique.
演算法 DFS
本文章將介紹兩種方法。
- 可以用DFS的cycle detection環路偵測演算法來偵測是否有擋修互卡的死結。
- 可以用BFS的Topological sort拓樸排序，來檢查是存在擋修互卡的死結。
- 可以用DFS的cycle detection環路偵測演算法
每個節點對應到課程，每個先修關係對應到一條邊。
造一個loop，從編號小的節點開始進行DFS深度優先拜訪。
假如遇到當下這個節點是Checking狀態，代表存在死結，無法依照順序修完所有的課程。
假如當下這個節點尚未檢查過，把自己標記成Checking，接著遞迴呼叫DFS拜訪所有鄰居節點。
最後，假如都順利完成，把當下這個節點(也就是這門課程)標記為Completed。
image
image
image
image
程式碼 DFS的cycle detection環路偵測演算法
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Constant defined for course state
NOT_CHECKED, CHECKING, COMPLETED = 0, 1, 2
# -------------------------------
def has_deadlock( course )->bool:
if course_state[course] != NOT_CHECKED:
# There is a cycle(i.e., deadlock ) in prerequisites
return course_state[course] == CHECKING
# update current course as checking
course_state[course] = CHECKING
# check pre_course in DFS and detect whether there is deadlock
for pre_course in requirement[course]:
if has_deadlock( pre_course ):
# deadlock is found, impossible to finish all courses
return True
# update current course as completed
course_state[course] = COMPLETED
return False
# -------------------------------
# each course maintain a list of its own prerequisites
requirement = collections.defaultdict( list )
for course, pre_course in prerequisites:
requirement[course].append( pre_course )
# each course maintain a state among {NOT_CHECKED, CHECKING, COMPLETED}
# Initial state is NOT_CHECKED
course_state = [ NOT_CHECKED for _ in range(numCourses) ]
# Launch cycle (i.e., deadlock ) detection in DFS
for course_idx in range(0, numCourses):
if has_deadlock(course_idx):
# deadlock is found, impossible to finish all courses
return False
# we can finish all course with required order
return True
演算法 BFS
另一種就是Topological sort拓樸排序。
建造一個Queue，從沒有擋修的課程(in_degree = 0的節點)開始進行廣度優先搜索，移除這一輪沒有擋修的課程和對應的out-going edge，移除的同時，把下一輪沒有擋修的課程加入Queue中，反覆進行迭代。
最後，如果所有課程都移除完畢，而且沒有剩餘的課程，代表可以依照順序修完所有課程。否則，代表存在有擋修互卡的死結。
程式碼 BFS的Topological sort拓樸排序
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# each course maintain a list of its own dependency
relation = defaultdict( list )
# in degree of each course
# in degree stands for the number of preliminary courses
in_degree = defaultdict( int )
for course, pre_course in prerequisites:
# update relation
relation[pre_course].append( course )
# update in_degree
in_degree[course] += 1
# Topological sort on in_degree
bfs_q = deque()
for course_idx in range(0, numCourses):
if in_degree[course_idx] == 0:
bfs_q.append(course_idx)
finish_count = 0
while bfs_q:
# Finish current course
cur_course = bfs_q.popleft()
finish_count += 1
# Unlock some courses related to current course
for course in relation[cur_course]:
in_degree[course] -= 1
if in_degree[course] == 0:
# this course can be taken next round if it doesn't have preliminary course anymore
bfs_q.append( course )
return finish_count == numCourses
複雜度分析
時間複雜度:
O( V+E )
兩種方法皆為O(V+E)，點至多拜訪一次，邊也是至多拜訪一次。
空間複雜度:
O( V+E )
兩種方法皆為O(V+E)，包含對應的DFS遞迴深度 + table大小，或者BFS Queue長度 + table大小
關鍵知識點
- 把課程先修關係抽象化，轉為圖論中的節點(課程)和邊(先修關係)，把課程擋修的問題轉化為是否存在Cycle環路的問題。
- 圖論中的題目，假如沒有特殊限制或者還沒有具體的解題想法，先聯想到DFS和BFS，這兩個可以說是圖論中最泛用的演算法模板。
Reference:
[1] Python by DFS//BFS and cycle detection [w/ Graph ] - Course Schedule - LeetCode
