leetcode1 仓库中的 Course Schedule IV：课程先修可达性查询的五大解法完全指南（LeetCode 1462）

leetcode1 仓库中的 Course Schedule IV课程先修可达性查询的五大解法完全指南LeetCode 1462【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南基于仓库内的 course-schedule-iv 题解文档系统讲解 LeetCode 1462 Course Schedule IV 这道多查询先修课程可达性判断问题的五种典型解法朴素 DFS、DFS 哈希集合、DFS 记忆化、Kahn 拓扑排序与 Floyd-Warshall 传递闭包。读完本文后你将掌握有向图可达性查询从逐查询搜索到预处理 O(1) 查询的完整优化路径并能在仓库中的 Python 实现、Java 实现、Kotlin 实现、TypeScript 实现 与 Swift 实现 中对照验证每种思路的落地写法。问题定义题目给定numCourses门课程编号0到numCourses - 1和先修关系数组prerequisites其中prerequisites[i] [a, b]表示想修课程b必须先修课程a。再给定查询数组queries每个查询[u, v]询问u是否是v的先修课程直接或间接本质上是把一个有向图的多对可达性reachability问题节点是课程边是先修依赖a - b。五种解法都在回答同一个问题区别在于何时计算、计算多少、存储什么。本文的解法脉络来自 articles/course-schedule-iv.md该文档完整收录了五种解法在多语言下的实现仓库同时保留了各语言的真实提交文件README.md 中的完成度表格也标注了 1462 题 Java / Kotlin / Python 的完成状态可作为实现文件与文档相互印证。前置知识在动手之前原文档列出了五项应熟练运用的前置技能这里一并继承并说明其在本题中的落点图的表示Graph Representation从边对构建邻接表表示有向图。这是五种解法共同的第 0 步。深度优先搜索DFS递归遍历图以完成路径查找与可达性查询是解法 1、2、3 的核心。拓扑排序Kahns Algorithm基于入度的 BFS按依赖顺序处理节点是解法 4 的核心。记忆化Memoization缓存已算结果避免重复的 DFS 遍历是解法 3 的核心。Floyd-Warshall 算法用 O(V^3) 的 DP 计算全源传递闭包是解法 5 的核心。解法一暴力 DFS逐查询搜索直觉要判断课程 A 是否是课程 B 的先修课程只需判断先修图中是否存在从 A 到 B 的路径。从 A 出发做一次深度优先搜索探索所有从 A 可达的课程若遍历中到达 B则 A 确实是 B 的先修课程。算法步骤由prerequisites构建邻接表每门课程指向其直接后继即它是谁的前置对每个查询(u, v)从u出发执行 DFSDFS 中若到达v返回true否则递归探索所有邻居任一分支能到达v则返回true所有分支均未找到路径返回false。参考代码Pythonclass Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) - List[bool]: adj [[] for _ in range(numCourses)] for u, v in prerequisites: adj[u].append(v) def dfs(node, target): if node target: return True for nei in adj[node]: if dfs(nei, target): return True return False res [] for u, v in queries: res.append(dfs(u, v)) return res参考代码Javapublic class Solution { private ListInteger[] adj; public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { adj new ArrayList[numCourses]; for (int i 0; i numCourses; i) adj[i] new ArrayList(); for (int[] pre : prerequisites) adj[pre[0]].add(pre[1]); ListBoolean res new ArrayList(); for (int[] query : queries) { res.add(dfs(query[0], query[1])); } return res; } private boolean dfs(int node, int target) { if (node target) return true; for (int nei : adj[node]) { if (dfs(nei, target)) return true; } return false; } }复杂度时间复杂度$O((V E) \cdot m)$空间复杂度$O(V E m)$其中 $m$ 为查询数$V$ 为课程数$E$ 为先修边数。每个查询都可能触发一次完整的 $O(VE)$ 图遍历查询多时会退化为 TLE——这正是后续四种解法要解决的问题。解法二DFS 哈希集合预计算每门课的先修集合直觉不要为每个查询跑 DFS而是预先计算每门课的全部先修课程。对每门课程用 DFS 找出所有直接或间接需要先修的课程并存入一个集合之后任意查询退化为一次集合成员判断。算法步骤构建邻接表注意方向与解法一相反每门课程指向其直接先修课程adj[crs].append(prereq)对每门课程执行 DFS收集所有可达的先修课程到一个集合用prereqMap缓存这些集合避免重复计算每门课的先修集合包含它自身以及其所有直接先修课程的先修集合之并对每个查询(u, v)检查u是否在v的先修集合中。参考代码Pythonclass Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) - List[bool]: adj defaultdict(list) for prereq, crs in prerequisites: adj[crs].append(prereq) def dfs(crs): if crs not in prereqMap: prereqMap[crs] set() for prereq in adj[crs]: prereqMap[crs] | dfs(prereq) prereqMap[crs].add(crs) return prereqMap[crs] prereqMap {} for crs in range(numCourses): dfs(crs) res [] for u, v in queries: res.append(u in prereqMap[v]) return res关键行prereqMap[crs] | dfs(prereq)完成先修集合的并集合并crs的先修集合 自己 每个直接先修prereq的先修集合递归已经算好并被缓存。参考代码Javapublic class Solution { private ListInteger[] adj; private MapInteger, SetInteger prereqMap; public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { adj new ArrayList[numCourses]; prereqMap new HashMap(); for (int i 0; i numCourses; i) adj[i] new ArrayList(); for (int[] pre : prerequisites) adj[pre[1]].add(pre[0]); for (int crs 0; crs numCourses; crs) dfs(crs); ListBoolean res new ArrayList(); for (int[] query : queries) { res.add(prereqMap.get(query[1]).contains(query[0])); } return res; } private SetInteger dfs(int crs) { if (prereqMap.containsKey(crs)) return prereqMap.get(crs); SetInteger prereqs new HashSet(); for (int pre : adj[crs]) { prereqs.addAll(dfs(pre)); } prereqs.add(crs); prereqMap.put(crs, prereqs); return prereqs; } }复杂度时间复杂度$O(V \cdot (V E) m)$空间复杂度$O(V^2 E m)$每门课都可能维护一个规模至多 $V$ 的集合查询阶段降为 $O(m)$ 的 O(1) 均摊查找。解法三DFS 记忆化二维状态表直觉把课程 A 是否是课程 B 的先修课程的结论按课程对缓存。检查(A, B)时把结果存入二维表之后相同或在同一 DFS 过程中重复出现的课程对可以瞬间回答避免重复的图遍历。算法步骤构建邻接表方向为课程 - 直接先修课程创建二维记忆化表isPrereq初始化为-1未知对每条直接先修边(prereq, crs)直接置isPrereq[crs][prereq] True已知的true基例对每个查询(u, v)执行 DFS 检查u是否为v的先修DFS 中若isPrereq[crs][prereq]已计算直接返回否则检查所有直接先修若某个直接先修本身就是目标或其传递先修包含目标则标记并返回true所有分支都不成立标记false并返回。参考代码Pythonclass Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) - List[bool]: adj [[] for _ in range(numCourses)] isPrereq [[-1] * numCourses for _ in range(numCourses)] for prereq, crs in prerequisites: adj[crs].append(prereq) isPrereq[crs][prereq] True def dfs(crs, prereq): if isPrereq[crs][prereq] ! -1: return isPrereq[crs][prereq] 1 for pre in adj[crs]: if pre prereq or dfs(pre, prereq): isPrereq[crs][prereq] 1 return True isPrereq[crs][prereq] 0 return False res [] for u, v in queries: res.append(dfs(v, u)) return res参考代码Javapublic class Solution { private ListInteger[] adj; private int[][] isPrereq; public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { adj new ArrayList[numCourses]; isPrereq new int[numCourses][numCourses]; for (int i 0; i numCourses; i) { adj[i] new ArrayList(); Arrays.fill(isPrereq[i], -1); } for (int[] pre : prerequisites) { adj[pre[1]].add(pre[0]); isPrereq[pre[1]][pre[0]] 1; } ListBoolean res new ArrayList(); for (int[] query : queries) { res.add(dfs(query[1], query[0])); } return res; } private boolean dfs(int crs, int prereq) { if (isPrereq[crs][prereq] ! -1) { return isPrereq[crs][prereq] 1; } for (int pre : adj[crs]) { if (pre prereq || dfs(pre, prereq)) { isPrereq[crs][prereq] 1; return true; } } isPrereq[crs][prereq] 0; return false; } }复杂度时间复杂度$O(V \cdot (V E) m)$空间复杂度$O(V^2 E m)$二维表 $O(V^2)$ 的空间换来了每个课程对至多探索一次是解法二的集合版换成了布尔表版。解法四拓扑排序Kahns Algorithm直觉用拓扑排序保证处理某门课程时它的所有先修课程都已经处理完毕。处理课程时把自己 自己的全部先修传播给每个后继。这样每门课在出队时就累积了完整的先修集合。算法步骤构建邻接表方向为先修 - 课程adj[pre].add(crs)并统计每门课的indegree队列初始化放入所有indegree 0的课程没有先修的课每次出队一个课程node对其每个后继neighbor把node与isPrereq[node]的全部元素并入isPrereq[neighbor]isPrereq[neighbor].add(node); isPrereq[neighbor].update(isPrereq[node])indegree[neighbor] - 1归零则入队全部课程处理完后每门课都有了完整先修集合对每个查询(u, v)判断u in isPrereq[v]。参考代码Pythonclass Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) - List[bool]: adj [set() for _ in range(numCourses)] indegree [0] * numCourses isPrereq [set() for _ in range(numCourses)] for pre, crs in prerequisites: adj[pre].add(crs) indegree[crs] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) while q: node q.popleft() for neighbor in adj[node]: isPrereq[neighbor].add(node) isPrereq[neighbor].update(isPrereq[node]) indegree[neighbor] - 1 if indegree[neighbor] 0: q.append(neighbor) return [u in isPrereq[v] for u, v in queries]参考代码Javapublic class Solution { public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { ListSetInteger adj new ArrayList(); ListSetInteger isPrereq new ArrayList(); int[] indegree new int[numCourses]; for (int i 0; i numCourses; i) { adj.add(new HashSet()); isPrereq.add(new HashSet()); } for (int[] pre : prerequisites) { adj.get(pre[0]).add(pre[1]); indegree[pre[1]]; } QueueInteger q new LinkedList(); for (int i 0; i numCourses; i) { if (indegree[i] 0) q.offer(i); } while (!q.isEmpty()) { int node q.poll(); for (int neighbor : adj.get(node)) { isPrereq.get(neighbor).add(node); isPrereq.get(neighbor).addAll(isPrereq.get(node)); indegree[neighbor]--; if (indegree[neighbor] 0) q.offer(neighbor); } } ListBoolean res new ArrayList(); for (int[] query : queries) { res.add(isPrereq.get(query[1]).contains(query[0])); } return res; } }复杂度时间复杂度$O(V \cdot (V E) m)$空间复杂度$O(V^2 E m)$与解法二相比Kahn 法把递归收集改写为按拓扑序迭代传播天然规避了深度递归且一次遍历完成全部先修集合的构建是面试中最容易一次写对、也最推荐作为生产级写法的方案。解法五Floyd-Warshall 传递闭包直觉Floyd-Warshall 求有向图的全源可达性若从A到B经过任意中间课程K存在路径则A是B的先修。跑完算法后任意课程对都能 O(1) 直查。算法步骤创建全false的二维布尔矩阵把直接先修边标记为trueadj[pre][crs] True注意这里存的是pre 可达 crs对每个中间节点k遍历所有(i, j)对若i - k且k - j可达则把i - j标记为true对每个查询(u, v)直接返回matrix[u][v]。参考代码Pythonclass Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) - List[bool]: res [] adj [[False] * numCourses for _ in range(numCourses)] for pre, crs in prerequisites: adj[pre][crs] True for k in range(numCourses): for i in range(numCourses): for j in range(numCourses): adj[i][j] adj[i][j] or (adj[i][k] and adj[k][j]) for u, v in queries: res.append(adj[u][v]) return res参考代码Javapublic class Solution { public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { boolean[][] adj new boolean[numCourses][numCourses]; ListBoolean res new ArrayList(); for (int[] pre : prerequisites) { adj[pre[0]][pre[1]] true; } for (int k 0; k numCourses; k) { for (int i 0; i numCourses; i) { for (int j 0; j numCourses; j) { adj[i][j] adj[i][j] || (adj[i][k] adj[k][j]); } } } for (int[] q : queries) { res.add(adj[q[0]][q[1]]); } return res; } }复杂度时间复杂度$O(V^3 E m)$空间复杂度$O(V^2 E m)$实现最短、最不易出错查询 O(1)但 $V^3$ 的闭包计算与 $V$ 强相关。当 $V$ 大而 $E$ 稀疏时解法二/三/四通常更快当需要反复、随机地查询大量课程对时Floyd-Warshall 一次算完、后续零成本的特性最划算。五种解法横向对比解法核心思想时间复杂度空间复杂度适用场景1. 暴力 DFS每个查询独立 DFS$O((VE)\cdot m)$$O(VEm)$查询极少快速实现验证2. DFS 哈希集合每门课预计算先修集合$O(V\cdot(VE)m)$$O(V^2Em)$查询多需要保留具体先修集合3. DFS 记忆化二维表缓存课程对结论$O(V\cdot(VE)m)$$O(V^2Em)$查询有重复希望惰性计算4. Kahn 拓扑排序按拓扑序迭代传播先修集合$O(V\cdot(VE)m)$$O(V^2Em)$递归深度敏感场景推荐默认写法5. Floyd-Warshall全源传递闭包$O(V^3Em)$$O(V^2Em)$查询量极大 / 实现求最短符号含义沿用原文档约定$m$ 为查询数$V$ 为课程数$E$ 为先修边数。仓库中的既有实现源码级印证文档给出的解法在仓库中均有对应实现文件可逐语言对照python/1462-course-schedule-iv.py采用解法二DFS 哈希集合。其dfs(crs)与文档 Python 版逻辑一致——先并集合并各直接先修的prereqMap集合再prereqMap[crs].add(crs)把自身加入外层对0..numCourses-1逐课触发 DFS最后以u in prereqMap[v]回答查询。java/1462-course-schedule-iv.java是一个解法一的工程化变体邻接表按课程 - 直接先修方向构建hm.get(b).add(a)每个查询用全新的visited数组做防重 DFS命中直接先修即返回。它印证了逐查询 DFS这一思路在真实提交中的常见写法同时提醒读者没有跨查询记忆化时查询多仍是瓶颈。kotlin/1462-course-schedule-iv.kt采用解法二/三的融合写法——prerequisitesMap缓存课程 - 完整先修集合dfs(startCourse, currentCourse)从每门课出发向先修方向 DFS用if (currentCourse in (prerequisitesMap[startCourse] ?: hashSetOf())) return充当剪枝避免重复收集。typescript/1462-course-schedule-iv.ts同样走预计算先修集合路线cache: Mapnumber, Setnumber逐层合并邻居集合并cache.get(node).add(node)查询阶段cache.get(b).has(a)一次命中。swift/1462-course-schedule-iv.swiftprereqMap[crs]!.formUnion(dfs(pre))与文档解法二的|并集语义一一对应最后prereqMap[v]?.contains(u) ?? false兜底处理无先修的课。从源码结构看仓库中 Java 与其余四种语言选择了不同档次的优化逐查询 DFS vs 预计算集合恰好覆盖上表中第 1、2 档适合作为对照阅读材料。常见陷阱Common Pitfalls原文档最后归纳的三个易错点值得逐条对照自查1. 边方向建反prerequisites中的[a, b]表示课程a必须在b之前修即方向是a - b。建图方向取决于你的解法采用向前找后继还是向后找先修但必须与 DFS/查询语义一致。以解法二为例邻接表必须是课程 - 直接先修# 错误在向后查先修的解法里把边建成了课程 - 后继 for pre, crs in prerequisites: adj[pre].append(crs) # 这是解法一的方向用于判断 pre 可达 crs # 正确解法二/三中adj[crs] 存放 crs 的直接先修 for pre, crs in prerequisites: adj[crs].append(pre)若用解法一的adj[pre].append(crs)方向却按向后查先修语义去 DFS可达性结论将完全颠倒。2. 无记忆化地逐查询重跑 DFS每个查询都从零开始全新 DFS 会导致大量重复工作查询多时直接 TLE# 低效无记忆化每条查询都从图结构上重新开始 def dfs(node, target): if node target: return True for nei in adj[node]: if dfs(nei, target): return True return False # 每条查询 O(V E)共 O(m) 条查询 - O((V E) * m)缓解手段按性价比排序课程对记忆化解法三→ 预计算先修集合解法二/四→ 全量传递闭包解法五。3. 忽略孤立节点既无先修也不被任何课程依赖的节点同样是合法节点。若邻接表或prereqMap没有为它们做初始化例如 Python 中未预建空列表/空集合而直接adj[i].append(...)这些课出现在查询中就会抛出KeyError或IndexError。五种解法的参考代码都刻意对全部numCourses个编号做了初始化[[] for _ in range(numCourses)]、Array(repeating: [Int](), count: numCourses)等就是为了覆盖这一情况。小结Course Schedule IV 是有向图多对可达性查询的标准练习场从逐查询 DFS$O((VE)m)$到预计算先修集合与课程对记忆化$O(V(VE)m)$ 预处理 $O(m)$ 查询再到 Kahn 拓扑传播与 Floyd-Warshall 闭包$O(V^3)$ 一次算完五条路径清晰展示了用空间与预处理换查询时间的完整谱系。仓库文档 articles/course-schedule-iv.md 保留了各解法的多语言完整实现而 python、java、kotlin、typescript、swift 五份提交文件则从不同角度印证了这些思路的工程写法结合上文陷阱清单逐项排查边方向、记忆化与节点初始化即可稳定实现并通过本题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考