圖論應用經典 課程表 Course Schedule_Leetcode #207

Tim Mossholder on Unsplash

題目敘述

題目會給我們一個輸入陣列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 <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

演算法 DFS

本文章將介紹兩種方法。

1. 可以用DFS的cycle detection環路偵測演算法來偵測是否有擋修互卡的死結。
2. 可以用BFS的Topological sort拓樸排序，來檢查是存在擋修互卡的死結。

1. 可以用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大小

關鍵知識點

1. 把課程先修關係抽象化，轉為圖論中的節點(課程)和邊(先修關係)，把課程擋修的問題轉化為是否存在Cycle環路的問題。

1. 圖論中的題目，假如沒有特殊限制或者還沒有具體的解題想法，先聯想到DFS和BFS，這兩個可以說是圖論中最泛用的演算法模板。

Reference:

[1] Python by DFS//BFS and cycle detection [w/ Graph ] - Course Schedule - LeetCode