LeetCode课程表问题：Kahn算法与DFS环检测方案对比

首先明确核心前提：两种算法的时间复杂度均为O(V + E)（V为节点数量，E为边数量），空间复杂度也基本持平，不存在绝对的优劣，选型完全取决于实际需求和场景特征。 #

两种方案的特性差异 #

• DFS实现的环检测
  实现逻辑更轻量：仅需维护两个标记数组，分别记录「已访问过的节点」和「当前递归栈内的节点」，遍历过程中只要遇到递归栈内已存在的节点，即可直接判定存在环。
  适合快速判环场景：无需遍历完整张图，检测到环的瞬间就可以终止返回，如果你只需要知道「是否存在环」不需要额外产出，有环场景下DFS的返回速度通常更快。
  存在局限：递归实现的版本如果遇到深度极大的图，容易触发栈溢出，需要手动写迭代模拟栈的版本才能规避；且仅能判环，若需要拓扑排序序列需要额外处理逻辑。
• 基于BFS的Kahn算法
  核心基于入度统计实现：初始化时统计所有节点的入度，将入度为0的节点加入队列依次处理，每处理一个节点就将其相邻节点的入度减1，最终如果处理过的节点总数小于总节点数，即可判定存在环。
  额外价值更高：判环的同时可以直接输出合法的拓扑排序序列，刚好匹配课程表类问题的延伸需求（比如输出可行的选课顺序），一次遍历就能完成多个需求，代码复用性更强。
  稳定性更好：天然是迭代实现，没有递归栈溢出风险，面对节点规模极大的深图也能稳定运行。
  存在局限：必须遍历完所有可处理的节点才能最终判定是否有环，哪怕图的前几个节点就构成环，也需要走完整个流程才能得到结论。

为什么课程表问题普遍推荐Kahn算法 #

这和题目的需求属性直接相关：课程表类问题除了基础的「能否修完所有课程」的判环需求外，绝大多数变种题都要求输出可行的选课顺序，Kahn算法可以一次遍历同时满足两个需求，不需要额外加逻辑；且面试场景下Kahn的逻辑更直观，入度统计、队列处理的流程边界清晰，不容易写错，也更容易给面试官讲清楚逻辑。 #

最终选型建议 #

• 仅需快速判断是否存在环，无拓扑排序需求的场景，优先选DFS
• 需要同时输出拓扑序列，或是面对的图规模极大、可能触发递归栈溢出的场景，优先选Kahn算法

内容的提问来源于stack exchange，提问作者garfield the cat