1、题目描述
你这个学期必须选修 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 。这是不可能的。
2、初始思路
2.1 思路
建立n*n维数组，如果出现x=y或者course[y][x] = 1(考虑到一门课程不能作为本门课程的先行课程和两门课程不能互相作为对方的先行课程）
import numpy as np
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:course = np.zeros((numCourses, numCourses))for x, y in prerequisites:if x == y or course[y][x] == 1:return Falseelse:course[x][y] = 1return True2.2 犯错点
上述代码没有检测间接的循环依赖，例如prerequisites =[[1,0],[0,2],[2,1]]，如下图所示，其存在环，因此也不能成立。
3 优化算法1
3.1 思路
由上述错误可见，该代码的核心应为检测有向图中是否存在环，如果存在环则选课不成立。具体应为以下步骤：
（1）通过prerequisites先建立一个有向图，可用邻接表表示有向图。
*邻接表：
-
邻接表是一种表示图的数据结构。
-
对于有向图，邻接表存储每个顶点的出边（即从该顶点出发的边）。
-
例如，顶点 A 的邻接表可能包含 [B, C]，表示有两条边从 A 指向 B 和 C。
-
邻接表是表示稀疏图（边数远小于顶点数的平方）的常用方式，因为它节省空间。
-
邻接矩阵适合稠密图，但空间复杂度较高。
建立邻接表的方法：
- 确定图的顶点和边：如本题，顶点为课程的数量，边为prerequisites中存储的有序对。
- 初始化邻接表：使用字典或列表来存储邻接表，对于每个顶点，初始化一个空列表，用于存储它的邻居（即从该顶点出发的边指向的顶点）。
#字典表示
adjacency_list = {v: [] for v in vertices}"""v: [] for v in vertices：{key_expression: value_expression for item in iterable}
key_expression：生成字典键的表达式。
value_expression：生成字典值的表达式。
item：从 iterable 中取出的每个元素。
iterable：可迭代对象（如列表、集合、范围等）。"""#如果顶点是连续的整数（例如 0, 1, 2, 3），也可以使用列表，本题即使用列表进行表示：
graph = [[] for _ in range(numCourses)]- 遍历边并填充邻接表
for x, y in prerequisites:graph[x].append(y)（2）利用dfs算法检测有向图中是否存在环，如果存在环，则返回False，否则存在True。
定义三个状态：
-
0：未访问。 -
1：正在访问（当前 DFS 路径中正在访问该节点）。 -
2：已访问（该节点及其所有子节点已经处理完毕）。
如果发现一个节点正在被访问（状态为 1），说明存在环。
def cycle(node):if visit[node] == 1:return Trueelif visit[node] == 2:return Falsevisit[node] = 1for neighbor in graph[node]:if cycle(neighbor):return Truevisit[node] = 2return False3.2 完整代码
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:graph = [[] for _ in range(numCourses)]for x, y in prerequisites:graph[x].append(y)print(graph)visit = [0] * numCoursesdef cycle(node):if visit[node] == 1:return Trueelif visit[node] == 2:return Falsevisit[node] = 1for neighbor in graph[node]:if cycle(neighbor):return Truevisit[node] = 2return Falsefor i in range(numCourses):if cycle(i):return Falsereturn True4 优化算法2
4.1 思路
使用出度和入度的概念进行求解，核心思想是拓扑排序。具体包括以下步骤：
（1）构建邻接表和入度队列。
graph = [[] for _ in range(numCourses)]
for x, y in prerequisites:graph[x].append(y)indegree[y] += 1
indegree = [0] * numCourses（2）初始化队列，将入度为0的节点加到queue中。
queue = collections.deque()
for i in range(numCourses):if indegree[i] == 0:queue.append(i)（3）拓扑排序，将入度为0的节点依次弹出，同时，其相邻节点的入度减1，如果其入度减为0，则将其也加入到队列中。核心思想为先将没有先行课程的课程学完，以此判断是否能学完所有课程。
while queue:cur = queue.popleft()for neighbor in graph[cur]:indegree[neighbor] -= 1if indegree[neighbor] == 0:queue.append(neighbor)（4）检测环，即检测是否还存在入度不为0的节点，如果存在，说明存在环，也就是该课程安排不合理。可使用两种方法进行检测：
- 对indegree列表进行排序，检测其最大的值是否大于0：
indegree.sort()
if indegree[-1] > 0:return False
return True- 依次访问indegree中的值，以此判断是否存在大于0的值：
for i in indegree:if i > 0:return False
return True4.2 完整代码
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:graph = [[] for _ in range(numCourses)]indegree = [0] * numCoursesfor x, y in prerequisites:graph[x].append(y)indegree[y] += 1queue = collections.deque()for i in range(numCourses):if indegree[i] == 0:queue.append(i)while queue:cur = queue.popleft()for neighbor in graph[cur]:indegree[neighbor] -= 1if indegree[neighbor] == 0:queue.append(neighbor)""" indegree.sort()if indegree[-1] > 0:return Falsereturn True """for i in indegree:if i > 0:return Falsereturn True 
