拓扑排序教程

1️⃣ 拓扑排序简介

拓扑排序（Topological Sort） 是对有向图（DAG：Directed Acyclic Graph，有向无环图）的一种线性排序，使得对于每条边 u → v，节点 u 在排序中出现在 v 之前。

特点：

• 仅适用于 有向无环图（DAG）
• 可用于任务依赖、编译顺序、课程安排等问题

2️⃣ 适用场景

1. 任务调度/依赖问题

   • 软件构建顺序（编译依赖）
   • 项目管理（先做 A 再做 B）

2. 课程安排问题

   • 学校课程先修条件（如：要先修数学，再修物理）

3. 系统依赖

   • 包管理（npm、maven、pip）中安装顺序

4. 判断环路

   • 如果图中存在环，拓扑排序无法完成，可用于检测循环依赖

3️⃣ 原理核心

Kahn 算法（BFS 版本）

核心思想：

1. 统计每个节点的 入度（多少前置节点依赖它）
2. 将 入度为 0 的节点加入队列
3. 队列出队节点 → 遍历其出边 → 对每个邻居入度减 1
4. 入度变为 0 的邻居加入队列
5. 重复直到队列为空

关键点：

• 入度表维护依赖状态
• 队列保证 BFS 顺序处理无依赖节点
• 能判断图中是否存在环（未处理完所有节点说明有环）

4️⃣ Java 示例实现（Kahn算法 + HashMap）

import java.util.*;

/**
 * 拓扑排序算法（Kahn算法实现）
 * 使用 HashMap<Integer, List<Integer>> 记录依赖（谁完成后触发哪些任务）
 * 适用于有向无环图（DAG）
 */
public class TopologicalSortHashMap {

    /**
     * @param n 图中节点个数（编号从1到n）
     * @param edges 边的集合，每条边为 {from, to}，表示 from → to（有向边）
     * @return 拓扑排序后的节点顺序（List）
     */
    public static List<Integer> topoSort(int n, int[][] edges) {

        // 1️⃣ 创建邻接表（HashMap：key=任务id，value=依赖它的任务列表）
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // 2️⃣ 创建入度表（每个任务还有多少前置任务未完成）
        Map<Integer, Integer> inDegree = new HashMap<>();

        // 3️⃣ 构建图结构 & 统计每个节点的入度
        for (int[] e : edges) {
            int from = e[0];
            int to = e[1];

            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
            inDegree.putIfAbsent(from, 0);
            inDegree.put(to, inDegree.getOrDefault(to, 0) + 1);
        }

        // 4️⃣ 初始化队列（入度为0的节点）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree.getOrDefault(i, 0) == 0) queue.offer(i);
        }

        // 5️⃣ 存储拓扑排序结果
        List<Integer> result = new ArrayList<>();

        // 6️⃣ BFS 循环处理
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            result.add(cur);
            for (int next : graph.getOrDefault(cur, Collections.emptyList())) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) queue.offer(next);
            }
        }

        // 7️⃣ 判断是否有环
        if (result.size() != n) throw new RuntimeException("❌ 图中存在环，无法进行拓扑排序！");

        return result;
    }

    // 🌟 示例主函数
    public static void main(String[] args) {
        int n = 4;
        int[][] edges = { {1, 2}, {1, 4}, {2, 3} };
        List<Integer> order = topoSort(n, edges);
        System.out.println("✅ 拓扑排序结果：" + order);
    }
}

5️⃣ 常见题型

1. 课程安排类 - LeetCode 210: 课程表 II
2. 任务调度类 - 项目任务依赖顺序
3. 路径依赖类 - 包安装顺序、模块加载顺序
4. 环检测 - 拓扑排序失败即存在环
5. 最大/最小耗时问题 - DAG 上求最长路径/关键路径问题

6️⃣ 小技巧与注意点

1. 节点编号不连续 → 用 HashMap 存储邻接表和入度
2. 多个解 → BFS 版本拓扑排序不是唯一的
3. 环检测 → BFS 未处理完所有节点或 DFS 遇到回边
4. 大规模图 → 用数组代替 HashMap（节省空间和时间）