刷题记载 HOT100 图论-3：207. 课程表
题目：207. 课程表难度：中等
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，此中 prerequisites = ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
[*]例如，先修课程对 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成全部课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
<strong>输入：</strong>numCourses = 2, prerequisites = []
<strong>输出：</strong>true
<strong>解释：</strong>总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 示例 2：
<strong>输入：</strong>numCourses = 2, prerequisites = [,]
<strong>输出：</strong>false
<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（卡恩算法）
class Solution:
def canFinish(self, numCourses: int, prerequisites: List]) -> bool:
inDegree = * numCourses
toMap = collections.defaultdict(list)
for ch in prerequisites:
i, o = ch, ch
inDegree += 1
toMap.append(i)
ans = 0
que = collections.deque()
for i in range(numCourses):
if inDegree == 0: que.append(i)
while que:
node = que.popleft()
ans += 1
for i in toMap:
inDegree -= 1
if inDegree == 0: que.append(i)
# print(ans, numCourses)
return ans == numCourses 2.DFS
class Solution:
def canFinish(self, numCourses: int, prerequisites: List]) -> bool:
def dfs(q):
nonlocal valid
visited = 1
for v in toMap:
if visited == 0:
dfs(v)
if not valid: return
elif visited == 1:
valid = False
return
visited = 2
# result.append(q)
valid = True
# result = []
visited = * numCourses
toMap = defaultdict(list)
for ch in prerequisites: toMap].append(ch)
i = 0
while i < numCourses and valid:
dfs(i)
i += 1
return valid
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]