前言

在图论算法中，拓扑排序是专门针对有向无环图（DAG） 的经典算法，也是笔试、蓝桥杯、面试高频考点。
日常开发与生活中处处都是拓扑排序的思想：

1. 大学选课：必须先修高数，才能修概率论；
2. 工程打包：Maven/Gradle 依赖加载顺序；
3. 任务调度：流水线任务先后执行顺序；
4. 编译原理：代码文件依赖编译顺序。

一、基础概念铺垫

1. 有向图

边具备方向性

u->v

代表单向依赖，不可逆。

2. 入度

以当前节点为终点的边的数量。

例：a -> b、c -> b，则 b 的入度为 2

3. 出度

以当前节点为起点的边的数量。

例：a -> b、a -> c，则 a 的出度为 2

4. 邻接表

图最常用存储方式，适合稀疏图，Java 中用 List<List<Integer>> 快速实现。

二、核心定义

给定一张有向图，若存在一个顶点序列，使得图中任意一条有向边

u→v

都满足：u 在序列中一定出现在 v 前面，该序列即为拓扑序，生成该序列的过程就是拓扑排序。
关键前提

• 只有有向无环图 (DAG) 才有合法拓扑序；
• 若图中存在环，必然无法完成拓扑排序（循环依赖）；
• 一张 DAG 的拓扑序不唯一。

三、算法详解

方案一：Kahn 算法（BFS 广度优先）

核心原理

• 统计所有节点入度，构建邻接表存储图关系；
• 把所有入度 = 0 的节点加入队列；
• 不断取出队首节点，加入拓扑结果集；
• 删除该节点的所有出边，对应邻接点入度 - 1；
• 若邻接点入度变为 0，再次入队循环；
• 最终比对：结果集大小 == 总节点数 → 无环；否则存在环。

代码示例

import java.util.*;
public class TopoSortKahn {
    // 拓扑排序主方法，返回完整拓扑序列，有环返回空数组
    public static int[] topoSort(int n, int[][] edges) {
        // 1. 构建邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        // 2. 维护入度数组
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adj.get(from).add(to);
            inDegree[to]++;
        }
        // 3. 初始化队列，存入所有入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 4. BFS遍历生成拓扑序
        int[] res = new int[n];
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res[count++] = cur;
            // 遍历当前节点所有后继节点
            for (int next : adj.get(cur)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        // 5. 环检测：count != n 说明有环
        return count == n ? res : new int[0];
    }
    
    public static void main(String[] args) {
        // 测试用例：5个节点
        int nodeNum = 5;
        // 边关系：0→1 0→2 1→3 2→3 3→4
        int[][] edges = {{0,1},{0,2},{1,3},{2,3},{3,4}};
        int[] topoArr = topoSort(nodeNum, edges);
        if (topoArr.length == 0) {
            System.out.println("图存在环路，无法拓扑排序");
        } else {
            System.out.println("Kahn算法-拓扑排序结果：");
            System.out.println(Arrays.toString(topoArr));
        }
    }
}

实例

原题链接：
207. 课程表 - 力扣（LeetCode）

首先，我把课程之间的先修关系转换成有向图，用邻接表存储每个课程的后继课程，同时用入度数组记录每个课程需要的先修课程数量。

然后，把所有入度为 0、没有先修要求的课程加入队列，这些是可以直接开始学的课程。接下来开始 BFS 遍历：每次从队列取出一门课程，代表已经学完，计数加一；然后把它所有后继课程的入度减一，如果后继课程入度变为 0，就加入队列继续学习。

最后，判断学完的课程数量是否等于总课程数。相等说明没有环，可以完成所有课程；不相等说明存在循环，无法完成。

最终代码如下：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 定义邻接表：key=课程编号，value=依赖这门课的后续课程列表
        HashMap<Integer, List<Integer>> adj = new HashMap<>();     
        // 2. 入度数组：记录每门课有多少先修课（没修完先修课就不能学这门）
        int[] inDegree = new int[numCourses];
        // 3. 初始化邻接表：给每一门课程都创建一个空的后续课程列表
        for (int i = 0; i < numCourses; i++) {
            adj.put(i, new ArrayList<>());
        }
        // 4. 遍历先修关系，构建图和入度
        // prerequisites 格式：[a, b] 表示 想学a，必须先学b
        for (int[] edge : prerequisites) {
            int a = edge[0]; // 要学的课程
            int b = edge[1]; // 先修课程
            
            // b 学完后才能学 a → 把 a 加入 b 的邻接表
            adj.get(b).add(a);
            // a 的入度+1（a多了一门先修课）
            inDegree[a]++;
        }
        // 5. BFS队列：存放入度为0的课程（没有先修课，可以直接学）
        Queue<Integer> queue = new LinkedList<>();
        // 6. 把所有没有先修课的课程（入度=0）加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 7. 统计已经学完的课程数量
        int visited = 0;
        // 8. BFS循环：学完一门课，就把它的后续课程的先修课数量-1
        while (!queue.isEmpty()) {
            // 取出一门可以学的课
            int u = queue.poll();
            // 学完了，计数+1
            visited++;
  
            // 遍历这门课的所有后续课程
            for (int v : adj.get(u)) {
                // 后续课程的先修课数量-1（因为刚学完了一门）
                inDegree[v]--;            
                // 如果后续课程的先修课都学完了（入度=0），加入队列
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        // 9. 如果学完的课程数 == 总课程数 → 无环，可以修完
        return visited == numCourses;
    }
}

方案二：DFS 深度优先实现拓扑排序

核心原理

1. 遍历所有未访问节点，递归进行深度优先搜索；
2. 递归回溯阶段（当前节点所有后继都遍历完毕），将节点压入栈；
3. 栈反转后，即为合法拓扑序列；
4. 通过递归标记位区分：未访问、访问中、已完成，以此检测环路。

状态标记

• 0：未访问
• 1：访问中（递归栈内，遇到该状态说明有环）
• 2：遍历完成

代码示例

import java.util.*;

public class TopoSortDfs {
    static List<List<Integer>> adj;
    static int[] status;
    static Deque<Integer> stack;
    static boolean hasCycle = false;

    public static int[] topoSort(int n, int[][] edges) {
        // 初始化
        adj = new ArrayList<>();
        status = new int[n];
        stack = new LinkedList<>();
        hasCycle = false;

        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }

        // 遍历所有节点
        for (int i = 0; i < n; i++) {
            if (status[i] == 0) {
                dfs(i);
            }
        }

        // 有环直接返回空
        if (hasCycle) {
            return new int[0];
        }
        // 栈弹出转为数组
        int[] res = new int[n];
        int idx = 0;
        while (!stack.isEmpty()) {
            res[idx++] = stack.pop();
        }
        return res;
    }

    private static void dfs(int cur) {
        // 标记为正在访问
        status[cur] = 1;
        // 遍历后继节点
        for (int next : adj.get(cur)) {
            if (status[next] == 1) {
                // 遇到递归栈节点，存在环
                hasCycle = true;
                return;
            }
            if (status[next] == 0) {
                dfs(next);
            }
        }
        // 遍历完成，标记+入栈
        status[cur] = 2;
        stack.push(cur);
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{0,2},{1,3},{2,3},{3,4}};
        int[] res = topoSort(n, edges);
        System.out.println("DFS-拓扑排序结果：");
        System.out.println(Arrays.toString(res));
    }
}

实例

将上个BFS解决的题目用DFS来解决

class Solution {
    // 标记状态：0未访问 1正在访问(递归栈中) 2已访问完成
    int[] status;
    // 邻接表
    HashMap<Integer, List<Integer>> adj;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        adj = new HashMap<>();
        status = new int[numCourses];
        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adj.put(i, new ArrayList<>());
        }

        // 构建有向图：[a,b]  b -> a  先修b才能学a
        for (int[] edge : prerequisites) {
            int a = edge[0];
            int b = edge[1];
            adj.get(b).add(a);
        }
        // 遍历每一个节点，逐个DFS判断是否有环
        for (int i = 0; i < numCourses; i++) {
            // 遇到环直接返回false
            if (!dfs(i)) {
                return false;
            }
        }
        // 全部遍历完无环，可以修完课程
        return true;
    }

    // DFS：返回false代表遇到环
    private boolean dfs(int cur) {
        // 1. 当前节点正在遍历，又回头访问 = 存在环
        if (status[cur] == 1) {
            return false;
        }
        // 2. 当前节点已经遍历完成，无需重复处理
        if (status[cur] == 2) {
            return true;
        }
        // 标记为正在访问
        status[cur] = 1;
        // 遍历当前节点所有后继课程
        for (int next : adj.get(cur)) {
            if (!dfs(next)) {
                return false;
            }
        }
        // 递归结束，标记为已访问完成
        status[cur] = 2;
        return true;
    }
}

四、两种算法对比

对比维度	Kahn(BFS)	DFS 拓扑排序
理解难度	简单，入门首选	稍难，依赖递归回溯
环检测	结果集数量判断	三色标记法判断
空间消耗	入度数组 + 队列	递归栈 + 状态数组
适用场景	算法笔试、工程依赖	深度图遍历、复杂图问题
时间复杂度	O(V+E)	O(V+E)

注：V 为顶点数，E为边数，两种算法效率一致。

五、常见易错点总结

1. 建图方向错误
   依赖关系极易写反：如先修b才能学a，正确建边为 b → a，很多人误写为 a → b，直接导致拓扑序完全错误。
2. 环判定逻辑混淆

• Kahn：最终遍历节点数不等于总节点数 → 有环

• DFS：遇到「访问中 (状态 1)」的节点 → 有环

  切勿混用两种判断逻辑。

3. DFS 三色状态漏更新
   递归回溯后必须将节点标记为已完成 (状态 2)，否则会重复遍历、误判环路，造成死递归或结果错误。
4. 孤立节点遗漏
   图中存在无入度、无出度的孤立点，初始化时需要统一加入队列 / 遍历，否则统计数量不足，误判存在环。
5. 多拓扑序认知误区
   DAG 的拓扑序不唯一，题目未要求字典序 / 特定规则时，合法序列均可得分，不用强行固定顺序。

六、总结

1. 拓扑排序是DAG 专属算法，核心作用：解决依赖约束、判断循环依赖、推导先后顺序；
2. Kahn(BFS) 上手简单、逻辑直观，适合竞赛快速写模板、环检测、输出常规拓扑序，优先掌握；
3. DFS 版拓扑 依托回溯与三色标记，适合复杂环检测、逆向推导、关键路径类问题；