【图解】拓扑排序（210. 课程表 II）
思路
这是一个典型的拓扑排序题目， 对拓扑排序不熟悉的，可以看下这个文章 - 揭开「拓扑排序」的神秘面纱，可以说讲的非常详细了。
Ok，我们回到这道题。以题目例2来说：
由于题目本身课程的依赖关系是这么给我们的：[[1,0],[2,0],[3,1],[3,2]] 这种数据格式我们不方便直接使用， 因此我们将其改造成图的一种表示方式邻接矩阵。
image.png
可以看到我们浪费了很多空间，这就是邻接矩阵的坏处， 而实际上对于这道题来说，没有必要真的搞一个邻接矩阵，比如这样就行了：
image.png
可以看出空间复杂度要更好一点。
构建矩阵的过程代码：
adjacent = [[] for _ in range(numCourses)]
for cur, pre in prerequisites:
adjacent[cur].append(pre)
接下来是算法的重点，我们对每一个课程进行一次深度遍历， 并且用visited数组记录每一个课程的访问状态，这样我们可以判断有没有环的存在，如果有环则返回[]。
而对于visited，我们使用三色标记法，即没有访问的，访问过但是没有访问完毕的以及完全访问完毕的标记不同颜色。在这里我用0表示没有访问过，1表示访问过但是没有访问完毕，2访问完毕。
DFS 核心逻辑：
def dfs(i):
# 访问过，还没访问完又回来了，说明有环
if visited[i] == 1:
return False
# 已经完全访问完毕，说明行得通
if visited[i] == 2:
return True
# 遍历前标记1
visited[i] = 1
for j in adjacent[i]:
if not dfs(j):
return False
# 遍历后标记2
visited[i] = 2
# 为2的都可以加入res了
res.append(i)
return True
关键点
- 拓扑排序
- 三色标记
代码
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
res = []
visited = [0] * numCourses
adjacent = [[] for _ in range(numCourses)]
def dfs(i):
if visited[i] == 1:
return False
if visited[i] == 2:
return True
visited[i] = 1
for j in adjacent[i]:
if not dfs(j):
return False
visited[i] = 2
res.append(i)
return True
for cur, pre in prerequisites:
adjacent[cur].append(pre)
for i in range(numCourses):
if not dfs(i):
return []
return res
「复杂度分析」
- 时间复杂度：
，其中M为课程总数，N为先行课程总数。
- 空间复杂度：
，其中M为课程总数，N为先行课程总数。
更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。目前已经30K+ star啦。
大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
❝如果可以的话，点击阅读原文帮我点个赞呗～ ❞
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录