210. 课程表 II
Title
現在你總共有 n 門課需要選，記為 0 到 n-1。
在選修某些課程之前需要一些先修課程。
例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，返回你為了學完所有課程所安排的學習順序。
可能會有多個正確的順序，你只要返回一種就可以了。
如果不可能完成所有課程，返回一個空數組。
示例 1:
輸入: 2, [[1,0]]
輸出: [0,1]
解釋: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0。因此，正確的課程順序為 [0,1] 。
示例 2:
輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程。要學習課程 3，你應該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應該排在課程 0 之后。
因此，一個正確的課程順序是 [0,1,2,3] 。另一個正確的排序是 [0,2,1,3] 。
前言
本題是一道經典的「拓撲排序」問題。
給定一個包含 n 個節點的有向圖 G，我們給出它的節點編號的一種排列，如果滿足：對于圖 G 中的任意一條有向邊 (u, v)，u 在排列中都出現在 v 的前面。那么稱該排列是圖 GG 的「拓撲排序」。
根據上述的定義，我們可以得出兩個結論：
有了上述的簡單分析，我們就可以將本題建模成一個求拓撲排序的問題了：
- 將每一門課看成是一個節點；
- 如果想要學習課程A之前必須完成課程B，那么從B到A連接一條有向邊。
求出該圖的拓撲排序，就可以得到一種復合要求的課程學習順序。
下面介紹兩種求解拓撲排序的方法：
方法一：深度優先搜索DFS
思路
將深度優先搜索的流程和拓撲排序的求解聯系起來，用一個棧來存儲所有已經搜索完成的節點。
對于一個節點u，如果它的所有相鄰節點都已經搜索完成，那么在搜索回溯到u的時候，u本身也會變成一個已經搜索完成的節點。
這里的「相鄰節點」指的是從u出發通過一條有向邊可以到達的所有節點。
假設我們當前搜索到了節點 u，如果它的所有相鄰節點都已經搜索完成，那么這些節點都已經在棧中了，此時我們就可以把 u 入棧。
可以發現，如果我們從棧頂往棧底的順序看，由于 u 處于棧頂的位置，那么 u 出現在所有 u 的相鄰節點的前面，因此對于 u 這個節點而言，它是滿足拓撲排序的要求的。
這樣以來，我們對圖進行一遍深度優先搜索，當每個節點進行回溯的時候，我們把該節點放入棧中，最終從棧頂到棧底的序列就是一種拓撲排序。
算法
對于圖中的任意一個節點，它在搜索的過程中有三種狀態，即：
-
「未搜索」：我們還沒有搜索到這個節點；
-
「搜索中」：我們搜索過這個節點，但還沒有回溯到該節點，即該節點還沒有入棧，還有相鄰的節點沒有搜索完成）；
-
「已完成」：我們搜索過并且回溯過這個節點，即該節點已經入棧，并且所有該節點的相鄰節點都出現在棧的更底部的位置，滿足拓撲排序的要求。
通過上述的三種狀態，我們就可以給出使用深度優先搜索得到拓撲排序的算法流程，在每一輪的搜索搜索開始時，我們任取一個「未搜索」的節點開始進行深度優先搜索。
我們將當前搜索的節點 u 標記為「搜索中」，遍歷該節點的每一個相鄰節點 v：
-
如果 v 為「未搜索」，那么我們開始搜索 v，待搜索完成回溯到 u；
-
如果 v 為「搜索中」，那么我們就找到了圖中的一個環，因此是不存在拓撲排序的；
-
如果 v 為「已完成」，那么說明 v 已經在棧中了，而 u 還不在棧中，因此 u 無論何時入棧都不會影響到 (u, v) 之前的拓撲關系，以及不用進行任何操作。
當 u 的所有相鄰節點都為「已完成」時，我們將 u 放入棧中，并將其標記為「已完成」。
在整個深度優先搜索的過程結束后，如果我們沒有找到圖中的環，那么棧中存儲這所有的 n 個節點，從棧頂到棧底的順序即為一種拓撲排序。
Code
def findOrder_DFS(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:# 存儲有向圖edges = collections.defaultdict(list)# 標記每個節點的狀態：0=》未搜索，1=》搜索中，2=》已搜索visited = [0] * numCourses# 用列表來模擬棧，索引0為棧底，n-1為棧頂result = list()# 有向圖是否有環標志invalid = Falsefor info in prerequisites:edges[info[1]].append(info[0])def dfs(u: int):nonlocal invalid# 將節點標記為搜索中visited[u] = 1# 搜索相鄰節點for v in edges[u]:# 如果未搜索，那么搜索相鄰節點if visited[v] == 0:dfs(v)# 只要發現有環，立刻停止搜索if invalid:return# 如果搜索中，說明找到了環elif visited[v] == 1:invalid = Truereturn# 將節點標記為已搜索visited[u] = 2result.append(u)# 每次挑選一個未搜索的節點，開始進行深度優先搜索for i in range(numCourses):if not invalid and not visited[i]:dfs(i)if invalid:return list()return result[::-1]復雜度分析
-
時間復雜度: O(n + m)，其中 n 為課程數，m 為先修課程的要求數。這其實就是對圖進行深度優先搜索的時間復雜度。
-
空間復雜度: O(n + m)。題目中是以列表形式給出的先修課程關系，為了對圖進行深度優先搜索，我們需要存儲成鄰接表的形式，空間復雜度為 O(m)。在深度優先搜索的過程中，我們需要最多 O(n) 的?？臻g（遞歸）進行深度優先搜索，并且還需要若干個 O(n) 的空間存儲節點狀態、最終答案等。
方法二：廣度優先搜索BFS
思路
方法一的深度優先搜索是一種「逆向思維」：最先被放入棧中的節點是在拓撲排序中最后面的節點。
我們也可以使用正向思維，順序地生成拓撲排序，這種方法也更加直觀。
我們考慮拓撲排序中最前面的節點，該節點一定不會有任何入邊，也就是它沒有任何的先修課程要求。
當我們將一個節點加入答案中后，我們就可以移除它的所有出邊，代表著它的相鄰節點少了一門先修課程的要求。
如果某個相鄰節點變成了「沒有任何入邊的節點」，那么就代表著這門課可以開始學習了。
按照這樣的流程，我們不斷地將沒有入邊的節點加入答案，直到答案中包含所有的節點（得到了一種拓撲排序）或者不存在沒有入邊的節點（圖中包含環）。
上面的想法類似于廣度優先搜索，因此我們可以將廣度優先搜索的流程與拓撲排序的求解聯系起來。
算法
我們使用一個隊列來進行廣度優先搜索。
初始時，所有入度為 0 的節點都被放入隊列中，它們就是可以作為拓撲排序最前面的節點，并且它們之間的相對順序是無關緊要的。
在廣度優先搜索的每一步中，我們取出隊首的節點 u：
我們將 u 放入答案中；
我們移除 u 的所有出邊，也就是將 uu 的所有相鄰節點的入度減少 1。如果某個相鄰節點 v 的入度變為 0，那么我們就將 v 放入隊列中。
在廣度優先搜索的過程結束后，如果答案中包含了這 n 個節點，那么我們就找到了一種拓撲排序，否則說明圖中存在環，也就不存在拓撲排序了。
Code
def findOrder_BFS(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:# 存儲有向圖edges = collections.defaultdict(list)# 存儲每個節點的入度indeg = [0] * numCourses# 存儲答案result = list()for info in prerequisites:edges[info[1]].append(info[0])indeg[info[0]] += 1# 將所有入度為 0 的節點放入隊列中queue = collections.deque([u for u in range(numCourses) if indeg[u] == 0])while queue:# 從隊首取出一個節點u = queue.popleft()result.append(u)for v in edges[u]:indeg[v] -= 1if indeg[v] == 0:queue.append(v)if len(result) != numCourses:result = list()return result復雜度分析
-
時間復雜度: O(n + m)，其中 n 為課程數，m 為先修課程的要求數。這其實就是對圖進行廣度優先搜索的時間復雜度。
-
空間復雜度: O(n + m)。題目中是以列表形式給出的先修課程關系，為了對圖進行廣度優先搜索，我們需要存儲成鄰接表的形式，空間復雜度為 O(m)。在廣度優先搜索的過程中，我們需要最多 O(n) 的隊列空間（迭代）進行廣度優先搜索，并且還需要若干個 O(n) 的空間存儲節點入度、最終答案等。
總結
以上是生活随笔為你收集整理的210. 课程表 II的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 用70行代码实现日志分析程序
- 下一篇： 152. 乘积最大子数组