拓扑排序是图论中的经典算法，主要用于解决有向无环图（Directed Acyclic Graph，简称 DAG）中的任务依赖关系问题。例如，课程学习顺序、项目任务调度、构建系统编译顺序等场景，都可以通过拓扑排序确定合理的执行流程。

Java实现拓扑排序通常有两种主流方式：Kahn算法（基于入度的广度优先搜索）和DFS深度优先遍历算法。两种方法思路不同，但最终目标都是生成一个满足依赖关系的线性排序结果。

一、什么是拓扑排序

拓扑排序是对一个有向图中的所有顶点进行排序，使得对于图中的每一条有向边：

A -> B

顶点 A 在排序结果中一定出现在顶点 B 的前面。

例如：

学习Java基础 -> 学习Spring框架 -> 开发Java项目

对应的拓扑排序结果可能为：

Java基础, Spring框架, Java项目开发

需要注意的是，只有有向无环图（DAG）才存在拓扑排序。如果图中存在环：

A -> B -> C -> A

那么任何节点都无法作为起点完成排序。

拓扑排序主要应用于：

• 项目任务依赖分析

• Maven、Gradle依赖管理

• 编译顺序确定

• 课程选修安排

• 数据处理流程设计

• 工作流调度系统

二、拓扑排序核心概念

实现拓扑排序前，需要理解几个关键概念。

1. 入度

入度表示一个节点被多少条边指向。

例如：

A -> C
B -> C

节点 C 的入度为 2，因为有 A 和 B 两个节点指向它。

在Kahn算法中，入度是最核心的数据。

2. 出度

出度表示一个节点指向其他节点的数量。

例如：

A -> B
A -> C

节点 A 的出度为2。

DFS算法主要利用节点访问状态以及递归结束顺序完成排序。

3. 有向无环图

拓扑排序只能应用于DAG。

判断一个图是否存在环，也是拓扑排序的重要用途之一。

如果最终排序结果中的节点数量小于图中节点总数，则说明图中存在环。

三、Kahn算法实现拓扑排序

Kahn算法是一种基于BFS思想的拓扑排序方法。

核心步骤：

1. 统计所有节点入度。

2. 找出所有入度为0的节点加入队列。

3. 不断取出队列节点加入结果。

4. 删除该节点产生的影响，使相邻节点入度减1。

5. 如果某个节点入度变成0，则加入队列。

6. 判断最终排序数量是否等于节点数量。

Java实现Kahn算法

假设有如下依赖关系：

0 -> 1
0 -> 2
1 -> 3
2 -> 3

代码实现：

Java
import java.util.*;

public class TopologicalSortKahn {

    public static List<Integer> topoSort(int n, int[][] edges) {

        // 保存邻接表
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 保存入度
        int[] indegree = new int[n];

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];

            graph.get(from).add(to);
            indegree[to]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        // 找入度为0的节点
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {

            int node = queue.poll();

            result.add(node);

            // 删除当前节点影响
            for (int next : graph.get(node)) {

                indegree[next]--;

                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }


        // 判断是否存在环
        if (result.size() != n) {
            return new ArrayList<>();
        }

        return result;
    }


    public static void main(String[] args) {

        int[][] edges = {
                {0, 1},
                {0, 2},
                {1, 3},
                {2, 3}
        };

        System.out.println(topoSort(4, edges));
    }
}

输出：

[0, 1, 2, 3]

Kahn算法复杂度分析

假设：

• V表示节点数量

• E表示边数量

时间复杂度：

O(V + E)

原因：

• 每个节点入队和出队一次。

• 每条边只会被访问一次。

空间复杂度：

O(V + E)

主要用于：

• 邻接表

• 入度数组

• 队列

四、DFS实现拓扑排序

DFS拓扑排序利用深度优先搜索完成。

核心思想：

如果一个节点依赖其他节点，那么它必须等待所有依赖节点处理完成后才能加入结果。

因此：

1. 深度搜索当前节点。

2. 递归访问所有后继节点。

3. 所有子节点完成后，将当前节点加入栈。

4. 最后反转栈得到拓扑顺序。

DFS判断环的方法

DFS实现必须记录节点状态。

通常使用三种状态：

如果DFS过程中遇到状态为1的节点，说明形成环。

例如：

A -> B -> C -> A

访问：

A(访问中)
B(访问中)
C(访问中)
再次访问A

发现A已经处于访问中状态，因此存在环。

Java实现DFS拓扑排序

Java
import java.util.*;

public class TopologicalSortDFS {


    private static List<List<Integer>> graph;

    private static int[] state;

    private static Stack<Integer> stack;


    public static List<Integer> topoSort(int n, int[][] edges) {


        graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }


        for (int[] edge : edges) {

            graph.get(edge[0])
                    .add(edge[1]);
        }


        state = new int[n];

        stack = new Stack<>();


        for (int i = 0; i < n; i++) {

            if (!dfs(i)) {
                return new ArrayList<>();
            }
        }


        List<Integer> result = new ArrayList<>();

        while (!stack.isEmpty()) {

            result.add(stack.pop());
        }


        return result;
    }



    private static boolean dfs(int node) {


        if (state[node] == 1) {

            //发现环
            return false;
        }


        if (state[node] == 2) {

            return true;
        }


        state[node] = 1;


        for (int next : graph.get(node)) {

            if (!dfs(next)) {

                return false;
            }
        }


        state[node] = 2;


        stack.push(node);


        return true;
    }


    public static void main(String[] args) {


        int[][] edges = {

                {0,1},
                {0,2},
                {1,3},
                {2,3}
        };


        System.out.println(
                topoSort(4, edges)
        );
    }
}

运行结果：

[0, 2, 1, 3]

DFS得到的拓扑序可能与Kahn算法不同，只要满足依赖关系即可。

五、Kahn算法和DFS算法对比

六、Java开发中的实际应用

1. Maven依赖解析

大型Java项目中，一个模块可能依赖多个模块：

common
 ↓
service
 ↓
web

构建工具需要通过拓扑排序确定编译顺序。

2. 课程学习顺序

例如：

数据结构 -> 算法
Java基础 -> Spring
Spring -> SpringBoot

通过拓扑排序可以生成合理学习路线。

3. 工作流系统

企业审批流程：

提交申请
 ↓
部门审核
 ↓
领导审批
 ↓
归档

每个任务都有前置条件，本质上就是拓扑排序问题。

七、拓扑排序常见问题

1. 为什么排序结果不唯一？

因为多个节点可能同时满足入度为0。

例如：

A -> C
B -> C

A和B都可以先执行。

因此：

A,B,C

和：

B,A,C

都是合法结果。

2. 如何判断图是否有环？

Kahn算法：

如果最终结果节点数量小于总节点数量：

result.size() < n

说明存在环。

DFS算法：

如果访问过程中遇到：

正在访问状态节点

说明存在环。

3. Kahn算法是否一定比DFS好？

并不是。

选择方式取决于场景：

• 需要明确检测环：DFS更直观。

• 需要任务调度过程：Kahn更自然。

• 图规模巨大：需要考虑DFS递归深度。

• 希望控制执行顺序：Kahn更容易扩展优先队列。

八、总结

Java实现拓扑排序主要有两种经典方案：

• Kahn算法：利用入度和队列，通过BFS思想完成排序，代码清晰，适合任务调度和依赖解析。

• DFS算法：利用递归和节点状态判断，通过后序遍历生成排序结果，适合图结构分析。

两种算法时间复杂度都为：

O(V + E)

掌握拓扑排序不仅能够解决算法题，也是理解构建系统、依赖管理、任务调度等实际工程问题的重要基础。

在Java项目开发中，根据业务需求选择合适的拓扑排序方式，可以有效处理复杂依赖关系，提高系统设计的可靠性和可维护性。