目录
题目
-
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
题解：BFS
- 利用有向无环图的入度。用一个字典存储节点（课程）和入度，每次将入度为0的加入队列，并且将后续课程的入度-1，每学完一门课就计数++。最后返回计数==课程数
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
#用字典存储有向图
edges = collections.defaultdict(list)
#存储每个节点的入度
indeg = [0] * numCourses
result = 0
# 初始化有向图的边和节点的入度
for info in prerequisites:
edges [info [1]].append(info[0]) # 将后续课程添加到前置课程的边列表中，建立了一个从前置课程指向后续课程的有向边。
indeg [info[0]]+=1 # 每当一个课程作为后续课程出现时，它的入度就会加 1。
# 创建一个双端队列，将入度为 0 的节点加入队列中
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
# 进行拓扑排序的过程
while q:
u=q.popleft() # 取出队列中的节点
result += 1 # 学完一门课程，result +1
# 遍历节点 u 的后续课程
for v in edges [u]:
indeg [v] -= 1# 将后续课程的入度 -1
if indeg[v] == 0:# 如果后续课程的入度为 0，将其加入队列
q.append(v)
return result == numCourses # 判断是否完成了所有课程
210.课程表Ⅱ
-
要求返回学习课程的顺序，其他条件同上
-
只需要把上面的统计课程的result换成列表，学完一门课就加入到result列表中，最后返回result列表
class Solution:
def findOrder(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 # 每当一个课程作为后续课程出现时，它的入度就会加 1。
# 创建一个双端队列，将入度为 0 的节点加入队列中
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
# 进行拓扑排序的过程
while q:
u=q.popleft() # 取出队列中的节点
result.append(u) # 学完一门课程，result +1
# 遍历节点 u 的后续课程
for v in edges [u]:
indeg [v] -= 1 # 将后续课程的入度 -1
if indeg[v] == 0: # 如果后续课程的入度为 0，将其加入队列
q.append(v)
if len(result) != numCourses: # 如果结果列表中的课程数量不等于总课程数，说明无法完成所有课程
result=list() # 将结果列表置空
return result # 判断是否完成了所有课程