【图-1】207.课程表

题目描述你这个学期必须选修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 入度核心思路把课程看作节点先修关系看作有向边[1, 0]表示0 → 1先学 0再学 1如果图中有环说明存在循环依赖无法完成如果无环可以完成算法步骤Kahn 算法建图邻接表 入度数组入队把所有入度为 0 的节点加入队列BFS每次从队列取出一个节点把它指向的节点入度减 1如果减到 0 就入队判断如果遍历过的节点数等于总课程数说明无环返回true具体过程示例numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]图: 0 → 1 → 3 0 → 2 → 3 入度: [0, 1, 1, 2] BFS: 入队 0入度0 取出 0: 1入度减1→0入队2入度减1→0入队 取出 1: 3入度减1→1 取出 2: 3入度减1→0入队 取出 3: 完成 遍历了4个节点 总课程数 → true ✅numCourses 2, prerequisites [[1,0],[0,1]]图: 0 → 1 → 0有环 入度: [1, 1] 没有入度为0的节点队列为空 遍历了0个节点 ≠ 2 → false ✅代码实现class Solution { public: bool canFinish(int numCourses, vectorvectorint prerequisites) { // 建图邻接表 入度数组 vectorvectorint graph(numCourses); vectorint indegree(numCourses, 0); for (auto pre : prerequisites) { int course pre[0], prereq pre[1]; graph[prereq].push_back(course); // prereq → course indegree[course]; } // 入度为 0 的节点入队 queueint q; for (int i 0; i numCourses; i) { if (indegree[i] 0) { q.push(i); } } // BFS int count 0; // 已完成的课程数 while (!q.empty()) { int curr q.front(); q.pop(); count; for (int next : graph[curr]) { indegree[next]--; if (indegree[next] 0) { q.push(next); } } } return count numCourses; } };复杂度分析设V是课程数E是先修关系数。维度复杂度说明时间复杂度O(V E)每个节点和边各访问一次空间复杂度O(V E)邻接表 入度数组 队列方法二DFS 判断环核心思路用 DFS 遍历图用三种状态标记节点0未访问1正在访问在当前 DFS 路径上2已访问完成如果 DFS 过程中遇到状态为1的节点说明有环。代码实现class Solution { public: bool canFinish(int numCourses, vectorvectorint prerequisites) { vectorvectorint graph(numCourses); for (auto pre : prerequisites) { graph[pre[1]].push_back(pre[0]); } vectorint state(numCourses, 0); // 0未访问 1访问中 2已完成 for (int i 0; i numCourses; i) { if (hasCycle(graph, state, i)) { return false; } } return true; } private: bool hasCycle(vectorvectorint graph, vectorint state, int node) { if (state[node] 1) return true; // 遇到访问中的节点有环 if (state[node] 2) return false; // 已完成无环 state[node] 1; // 标记为访问中 for (int next : graph[node]) { if (hasCycle(graph, state, next)) { return true; } } state[node] 2; // 标记为已完成 return false; } };复杂度分析维度复杂度说明时间复杂度O(V E)每个节点和边各访问一次空间复杂度O(V E)邻接表 状态数组 递归栈两种方法对比方法时间复杂度空间复杂度代码复杂度推荐度BFS 拓扑排序O(V E)O(V E)中等⭐⭐⭐⭐⭐DFS 判断环O(V E)O(V E)中等⭐⭐⭐⭐BFS 的优势可以顺便输出拓扑序适合需要顺序的场景。DFS 的优势代码更简洁递归思路直观。总结要点说明核心思想判断有向图是否有环BFS 方法入度为 0 入队遍历后判断节点数DFS 方法三色标记遇到访问中的节点说明有环时间复杂度O(V E)空间复杂度O(V E)