看懂这篇文章，你就能理解80%的拓扑排序问题

大家好，我是忍者算法。今天要聊的这道题，困扰了无数求职者。但只要掌握了正确的思维方法，你会发现它其实很优雅。

🎓 从选课系统说起

小明最近在给弟弟规划大学课程，发现了一个有趣的问题：

• "要学高数2，得先学高数1"
• "要学数据结构，得先学C语言"
• "要学操作系统，得先学数据结构"

这不就是今天要解决的算法题吗？

💡 问题的本质

LeetCode 207题"课程表"的描述是这样的：

你总共需要修完 numCourses 门课程
prerequisites[i] = [ai, bi] 表示：想要学习课程 ai ，必须先完成课程 bi

判断是否可能完成所有课程的学习？

示例：
输入：numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
输出：true
解释：可以按照 0→1→2→3 的顺序学习

🤔 这题的关键是什么？

本质上，我们在判断：课程之间的依赖关系是否形成了"环"。

• 如果有环：比如 A依赖B、B依赖C、C依赖A，那就不可能完成
• 如果无环：就一定存在一种可行的学习顺序

这就是典型的拓扑排序问题！

🎬 模拟运行：看看算法是如何工作的

让我们用一个具体例子，一步步看清算法的运行过程：

课程数：4
依赖关系：[[1,0], [2,1], [3,2]]

Step 1: 构建邻接表和入度数组
课程0 → 被课程1依赖
课程1 → 被课程2依赖
课程2 → 被课程3依赖

入度统计：
课程0：0个依赖
课程1：1个依赖（依赖0）
课程2：1个依赖（依赖1）
课程3：1个依赖（依赖2）

Step 2: BFS遍历过程
第一轮：
- 入度为0的课程：[0]
- 将0加入队列
- 学习0后，课程1的入度减1（变为0）

第二轮：
- 入度为0的课程：[1]
- 将1加入队列
- 学习1后，课程2的入度减1（变为0）

第三轮：
- 入度为0的课程：[2]
- 将2加入队列
- 学习2后，课程3的入度减1（变为0）

第四轮：
- 入度为0的课程：[3]
- 将3加入队列
- 没有更多依赖需要解除

最终顺序：0 → 1 → 2 → 3
学习课程总数：4（等于课程总数，说明可行）

⚡ 代码实现：BFS解法

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表：每个课程所指向的后续课程
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        
        // 统计每个课程的入度（依赖数量）
        int[] inDegrees = new int[numCourses];
        
        // 填充邻接表和入度数组
        for (int[] pre : prerequisites) {
            int curr = pre[0];  // 当前课程
            int prev = pre[1];  // 前置课程
            adjacency.get(prev).add(curr);  // 添加依赖关系
            inDegrees[curr]++;  // 当前课程入度+1
        }
        
        // 将所有入度为0的课程加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) {
                queue.offer(i);
            }
        }
        
        // BFS遍历
        int count = 0;  // 记录已学习的课程数
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;  // 学习一门课程
            
            // 将当前课程的所有后续课程的入度减1
            for (int next : adjacency.get(course)) {
                inDegrees[next]--;
                // 如果某个后续课程的入度变为0，加入队列
                if (inDegrees[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        // 判断是否学完所有课程
        return count == numCourses;
    }
}

🎯 算法要点解析

拓扑排序的精髓在于：

1. 找到所有没有依赖的节点（入度为0）
2. 删除这些节点，并更新其他节点的依赖状态
3. 重复以上步骤，直到：
   • 所有节点都被删除（有解）
   • 或剩下的节点都有依赖（无解）

📊 复杂度分析

时间复杂度：O(N + E)

• N是课程数量
• E是依赖关系的数量

空间复杂度：O(N + E)

• 邻接表和队列的空间开销

🎯 面试官最爱追问

1. Q：如何输出一个可行的学习顺序？ A：只需要将BFS过程中的课程号按顺序记录下来

2. Q：能不能用DFS解决？ A：可以，通过检测环的方式实现

3. Q：如果有多个可行解，如何输出字典序最小的解？ A：将队列改为优先队列，按课程号排序

💡 举一反三

这个模板还可以解决：

• 任务调度
• 软件包依赖管理
• 项目构建顺序
• 施工工序安排

🎁 思考题

如果每门课程都有一个学习时长，求完成所有课程的最短时间？

例如：
课程时长：[3,2,4,1]（小时）
依赖关系：[[1,0],[2,1],[3,2]]

如果你知道答案，或者有自己的想法？欢迎在评论区留言、讨论～

📝 代码模板总结

拓扑排序的通用步骤：

1. 统计入度
2. 将入度为0的节点入队
3. BFS删除节点并更新入度
4. 判断是否所有节点都被删除

---

作者：忍者算法
公众号：忍者算法

📚 回复【刷题清单】获取更多BFS经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现

#算法面试 #LeetCode #图论 #拓扑排序