刷题记载 HOT100 图论-3：207. 课程表

题目：207. 课程表
难度：中等
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，此中 prerequisites = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
  

请你判断是否可能完成全部课程的学习？如果可以，返回 true ；否则，返回 false 。
 
示例 1：

1. <strong>输入：</strong>numCourses = 2, prerequisites = [[1,0]]
2. <strong>输出：</strong>true
3. <strong>解释：</strong>总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

复制代码

示例 2：

1. <strong>输入：</strong>numCourses = 2, prerequisites = [[1,0],[0,1]]
2. <strong>输出：</strong>false
3. <strong>解释：</strong>总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

复制代码

 
提示：

• 1 <= numCourses <= 2000
  
• 0 <= prerequisites.length <= 5000
  
• prerequisites.length == 2
  
• 0 <= ai, bi < numCourses
  
• prerequisites 中的全部课程对 互不相同
  

一、模式识别

1.图论

课程表是经典的图论中的拓扑排序题目
拓扑排序有两种实现方式：BFS（卡恩算法）和DFS
2.BFS（卡恩算法）思路

焦点思路：从入度为0的节点开始，每遍历一个节点删除一个节点，并不绝统计入度为0节点，如果统计结果小于总数，证明
算法步骤：
1.初始化：记载入度和节点间的关系
2.BFS找0入度节点，每找到一个，将其删除（将其指向的全部节点的入度减一），并计数
3.对比统计数与节点总数是否相等
3.DFS思路

焦点思路：从恣意节点开始，DFS搜刮路径，如果在某节点处搜刮返回了原位，则证明有环
算法步骤：
1.初始化：记载节点间关系，并用visited数组记载是否已访问
2.DFS（回溯法）从0号位开始搜刮路径，直到最后一号位，如果发现有环，则返回False
二、代码实现

1.BFS（卡恩算法）

1. class Solution:
2.     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3.         inDegree = [0] * numCourses
4.         toMap = collections.defaultdict(list)
5.         for ch in prerequisites:
6.             i, o = ch[0], ch[1]
7.             inDegree[i] += 1
8.             toMap[o].append(i)
9.         ans = 0
10.         
11.         que = collections.deque()
12.         for i in range(numCourses):
13.             if inDegree[i] == 0: que.append(i)
14.         
15.         while que:
16.             node = que.popleft()
17.             ans += 1
18.             for i in toMap[node]:
19.                 inDegree[i] -= 1
20.                 if inDegree[i] == 0: que.append(i)
22.         # print(ans, numCourses)
23.         return ans == numCourses

复制代码

2.DFS

1. class Solution:
2.     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3.         def dfs(q):
4.             nonlocal valid
5.             visited[q] = 1
6.             for v in toMap[q]:
7.                 if visited[v] == 0:
8.                     dfs(v)
9.                     if not valid: return
10.                 elif visited[v] == 1:
11.                     valid = False
12.                     return
13.             visited[q] = 2
14.             # result.append(q)
15.         
16.         valid = True
17.         # result = []
18.         visited = [0] * numCourses
19.         toMap = defaultdict(list)
20.         for ch in prerequisites: toMap[ch[1]].append(ch[0])
22.         i = 0
23.         while i < numCourses and valid:
24.             dfs(i)
25.             i += 1
26.         return valid

复制代码

 
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。