每日算法 — 使用java实现拓扑排序：Kahn算法与DFS逆后序的对比分析

引言

拓扑排序（Topological Sort）是对有向无环图（DAG）中所有节点进行线性排序的算法，要求对于图中的每一条有向边 $(u, v)$，节点 $u$ 在排序结果中始终位于节点 $v$ 之前。拓扑排序广泛应用于任务调度、课程选修计划、编译依赖分析、数据流处理等场景。本文将深入讲解两种经典实现：基于入度的Kahn算法和基于DFS的逆后序算法。

图的数据结构

import java.util.*;

public class DirectedGraph {
    private int vertices;
    private List<List<Integer>> adjList; // 邻接表

    public DirectedGraph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int from, int to) {
        adjList.get(from).add(to);
    }

    public List<Integer> getNeighbors(int v) {
        return adjList.get(v);
    }

    public int getVertices() { return vertices; }
}

Kahn算法：基于入度的BFS实现

Kahn算法的核心思想是 repeatedly 移除入度为0的节点。若最终所有节点都被移除，则存在拓扑排序；否则图中存在环。

public class TopologicalSortKahn {

    public static List<Integer> topoSort(DirectedGraph graph) {
        int n = graph.getVertices();
        int[] inDegree = new int[n];

        // 计算所有节点的入度
        for (int u = 0; u < n; u++) {
            for (int v : graph.getNeighbors(u)) {
                inDegree[v]++;
            }
        }

        // 将所有入度为0的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

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

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            // 移除u的所有出边，更新邻接节点入度
            for (int v : graph.getNeighbors(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 若结果中节点数不足，说明存在环
        if (result.size() != n) {
            throw new IllegalStateException("图中存在环，无法进行拓扑排序");
        }
        return result;
    }
}

DFS逆后序算法

DFS拓扑排序利用后序遍历的性质：当节点 $u$ 的所有后继节点都被访问后，才将 $u$ 加入结果。最终需将结果逆序。

public class TopologicalSortDFS {

    public static List<Integer> topoSort(DirectedGraph graph) {
        int n = graph.getVertices();
        boolean[] visited = new boolean[n];
        boolean[] onStack = new boolean[n]; // 用于检测环
        Deque<Integer> stack = new ArrayDeque<>(); // 模拟递归栈用于输出

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, i, visited, onStack, stack);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private static void dfs(DirectedGraph graph, int u, boolean[] visited,
                            boolean[] onStack, Deque<Integer> stack) {
        visited[u] = true;
        onStack[u] = true;

        for (int v : graph.getNeighbors(u)) {
            if (!visited[v]) {
                dfs(graph, v, visited, onStack, stack);
            } else if (onStack[v]) {
                // v在当前递归栈中，发现回边，存在环
                throw new IllegalStateException("图中存在环，无法进行拓扑排序");
            }
        }

        onStack[u] = false;
        stack.push(u); // 后序入栈
    }
}

课程选修计划：实际应用案例

假设有 $n$ 门课程，某些课程有先修要求，求合法的修课顺序。

public class CourseSchedule {

    // 判断是否能完成所有课程，并返回一种合法顺序
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        // 构建图
        DirectedGraph graph = new DirectedGraph(numCourses);
        for (int[] pre : prerequisites) {
            graph.addEdge(pre[1], pre[0]); // pre[1]是pre[0]的先修课
        }

        try {
            List<Integer> order = TopologicalSortKahn.topoSort(graph);
            int[] result = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                result[i] = order.get(i);
            }
            return result;
        } catch (IllegalStateException e) {
            return new int[0]; // 无法完成
        }
    }

    public static void main(String[] args) {
        // 课程0需要课程1作为先修，课程1需要课程2作为先修
        int[][] prerequisites = { {0, 1}, {1, 2} };
        int[] order = findOrder(3, prerequisites);
        System.out.println("修课顺序: " + Arrays.toString(order)); // [2, 1, 0]
    }
}

两种算法对比

字典序最小拓扑排序

在Kahn算法中将普通队列替换为优先队列（小顶堆），即可输出字典序最小的拓扑序列。

    public static List<Integer> topoSortLexicographically(DirectedGraph graph) {
        int n = graph.getVertices();
        int[] inDegree = new int[n];
        for (int u = 0; u < n; u++) {
            for (int v : graph.getNeighbors(u)) inDegree[v]++;
        }

        // 使用优先队列保证字典序最小
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) pq.offer(i);
        }

        List<Integer> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            int u = pq.poll();
            result.add(u);
            for (int v : graph.getNeighbors(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) pq.offer(v);
            }
        }
        return result;
    }

拓扑排序是处理有向图依赖关系的基础工具，无论是编译器的Makefile依赖解析，还是现代CI/CD流水线的任务编排，都离不开这一经典算法。