力扣实训 _ [207].课程表/图论

1. 题目回顾本题是经典的图论问题LeetCode 207. 课程表。核心要求给定numCourses门课程编号 0 到 numCourses-1和先修关系数组prerequisites判断是否可能完成所有课程的学习。本质转化将课程看作节点先修关系看作有向边判断该有向图中是否存在环。若存在环如 A 依赖 BB 依赖 A则无法完成若无环即有向无环图 DAG则可以完成。2. 核心思路拓扑排序与“入度归零”解决此类问题的核心在于拓扑排序。我们可以把修课过程想象成“剥洋葱”或“流水线生产”入度Indegree表示一门课有多少个前置依赖。例如[0, 1]表示学 0 之前必须先学 1此时课程 0 的入度为 1。核心逻辑只有当一门课的入度变为 0 时即所有前置课程都修完了这门课才能被选修。判环依据如果我们不断移除入度为 0 的课程最后发现还有课程剩余入度永远不为 0说明剩下的课程之间存在循环依赖无法完成。3. 算法详细步骤3.1 深度优先搜索 (DFS) 步骤这种方法通过递归遍历来检测“当前路径上”是否有环。构建邻接表建立从“先修课”指向“后续课”的映射关系。状态标记为每个节点维护三种状态0未访问。1正在访问中在当前递归栈中。如果再次遇到状态为 1 的节点说明发现了环。2已完成访问安全节点。递归检测对每个未访问节点启动 DFS。如果在递归过程中遇到状态为 1 的邻居直接返回 False。回溯标记当某节点的所有邻居都检查完毕且无环将其标记为 2。3.2 广度优先搜索 (BFS) / 入度表法步骤这是最直观的“模拟上课”过程也是通常所说的拓扑排序标准解法。统计入度与建图计算每门课的入度有多少先修课。建立邻接表记录每门课修完后能解锁哪些后续课程。初始化队列将所有入度为 0的课程加入队列这些是可以直接开始学的课。循环处理从队列取出一个课程计数器 1表示已修完。遍历该课程的后续课程将它们入度 -1。如果某后续课程入度变为 0说明其前置条件已全部满足加入队列。结果判定比较“已修课程数”与“总课程数”。若相等说明无环返回 True否则返回 False。4. 代码实现以下代码采用 Python 编写注重可读性。解法一BFS 入度表法import java.util.*; class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 初始化数据结构 // inDegree[i] 存储第 i 门课的先修课数量 int[] inDegree new int[numCourses]; // adj 存储邻接表adj[i] 包含修完 i 之后可以修的所有课程 ListListInteger adj new ArrayList(); for (int i 0; i numCourses; i) { adj.add(new ArrayList()); } // 2. 构建图和入度表 for (int[] pre : prerequisites) { int target pre[0]; // 目标课程 int source pre[1]; // 先修课程 // source - target adj.get(source).add(target); // 目标课程入度 1 inDegree[target]; } // 3. 将所有入度为 0 的课程加入队列 QueueInteger queue new LinkedList(); for (int i 0; i numCourses; i) { if (inDegree[i] 0) { queue.offer(i); } } // 4. BFS 过程 int count 0; // 记录已修完的课程数 while (!queue.isEmpty()) { int curr queue.poll(); // 拿出一门课来修 count; // 遍历这门课解锁的后续课程 for (int nextCourse : adj.get(curr)) { inDegree[nextCourse]--; // 前置任务少了一个 // 如果入度变为 0说明可以修这门课了 if (inDegree[nextCourse] 0) { queue.offer(nextCourse); } } } // 5. 判断是否所有课都能修完 return count numCourses; } }解法二DFS 状态标记法class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 构建邻接表 ListListInteger adj new ArrayList(); for (int i 0; i numCourses; i) { adj.add(new ArrayList()); } for (int[] pre : prerequisites) { adj.get(pre[1]).add(pre[0]); } // flags 数组用于标记节点状态 // 0: 未访问 // 1: 正在访问当前递归路径上- 发现环的标志 // -1: 已访问安全节点之前的路径已经确认无环 int[] flags new int[numCourses]; // 对每个节点进行 DFS 检测 for (int i 0; i numCourses; i) { if (!dfs(adj, flags, i)) { return false; } } return true; } private boolean dfs(ListListInteger adj, int[] flags, int i) { // 如果状态为 1说明在当前路径上遇到了自己有环 if (flags[i] 1) return false; // 如果状态为 -1说明之前已经检查过这条路是安全的无需重复检查 if (flags[i] -1) return true; // 标记为正在访问 flags[i] 1; // 递归访问所有邻居 for (int j : adj.get(i)) { if (!dfs(adj, flags, j)) { return false; } } // 当前节点及其所有后代都检查完毕没有环标记为安全 flags[i] -1; return true; } }5. 复杂度分析BFS 入度表法时间复杂度 O(NE)。其中 N 是课程数 E 是先修关系数。我们需要遍历所有节点和所有边各一次。空间复杂度 O(NE) 。需要存储邻接表 E 和入度数组 N 以及队列 N 。DFS 状态标记法时间复杂度 O(NE) 。每个节点和每条边最多被访问一次。空间复杂度 O(NE) 。除了存储图的空间外递归调用栈在最坏情况下链状图深度为 N 。