深入理解Java拓扑排序（从零开始掌握有向无环图的排序算法）

拓扑排序的核心思想

拓扑排序的关键在于：每次选择一个入度为0（即没有任何前置依赖）的节点，将其加入结果序列，并从图中移除该节点及其所有出边。重复此过程，直到图中没有节点为止。

如果最终结果中的节点数量少于原图的节点总数，说明图中存在环，无法进行拓扑排序。

Java实现拓扑排序（Kahn算法）

下面我们将使用Kahn算法来实现拓扑排序。该算法基于广度优先搜索（BFS）的思想，非常适合初学者理解。

import java.util.*;public class TopologicalSort {    // 使用邻接表表示图    private Map<Integer, List<Integer>> graph;    private int numVertices;    public TopologicalSort(int vertices) {        this.numVertices = vertices;        graph = new HashMap<>();        for (int i = 0; i < vertices; i++) {            graph.put(i, new ArrayList<>());        }    }    public void addEdge(int from, int to) {        graph.get(from).add(to);    }    public List<Integer> topologicalSort() {        // 计算每个节点的入度        int[] inDegree = new int[numVertices];        for (int u : graph.keySet()) {            for (int v : graph.get(u)) {                inDegree[v]++;            }        }        // 将所有入度为0的节点加入队列        Queue<Integer> queue = new LinkedList<>();        for (int i = 0; i < numVertices; i++) {            if (inDegree[i] == 0) {                queue.offer(i);            }        }        List<Integer> result = new ArrayList<>();        // BFS处理        while (!queue.isEmpty()) {            int u = queue.poll();            result.add(u);            // 移除u的所有出边            for (int v : graph.get(u)) {                inDegree[v]--;                if (inDegree[v] == 0) {                    queue.offer(v);                }            }        }        // 检查是否存在环        if (result.size() != numVertices) {            System.out.println("图中存在环，无法进行拓扑排序！");            return new ArrayList<>();        }        return result;    }    public static void main(String[] args) {        TopologicalSort g = new TopologicalSort(6);        g.addEdge(5, 2);        g.addEdge(5, 0);        g.addEdge(4, 0);        g.addEdge(4, 1);        g.addEdge(2, 3);        g.addEdge(3, 1);        List<Integer> order = g.topologicalSort();        System.out.println("拓扑排序结果: " + order);    }}

代码解析

• 图的表示：我们使用HashMap存储邻接表，key是节点，value是该节点指向的邻居列表。
• 入度计算：遍历所有边，统计每个节点的入度。
• 队列初始化：将所有入度为0的节点加入队列。
• BFS处理：依次取出节点，加入结果，并更新其邻居的入度。
• 环检测：若结果长度不等于总节点数，说明图中有环。

应用场景

拓扑排序在实际开发中非常有用，例如：

• Maven/Gradle 等构建工具中的依赖解析
• 操作系统中的任务调度
• 课程先修要求系统
• 编译器中的指令调度

总结

通过本教程，你已经掌握了如何用Java语言实现拓扑排序算法，并理解了它在有向无环图排序中的核心作用。无论你是准备面试还是开发实际项目，这项技能都非常实用。

记住：拓扑排序只适用于有向无环图（DAG）。如果你的图中存在环，算法会明确告诉你无法排序。

希望这篇Java图论教程对你有所帮助！动手试试修改代码，添加自己的测试用例吧。