每日算法 — 使用java实现拓扑排序：有向无环图的任务调度与Kahn算法

拓扑排序（Topological Sort）是对有向无环图（DAG）的节点进行线性排序的算法，使得对于图中的每一条有向边(u, v)，节点u在排序中始终位于节点v之前。拓扑排序广泛应用于任务调度、编译依赖解析、课程选修计划、Makefile构建顺序等场景。

核心思想

拓扑排序基于两个关键观察：

1. DAG中必然存在至少一个入度为0的节点（没有前置依赖的节点）
2. 移除一个入度为0的节点及其出边后，剩余图仍然是DAG

Kahn算法利用上述性质，反复移除入度为0的节点，直到所有节点被处理或发现环。

Kahn算法步骤

1. 计算所有节点的入度
2. 将所有入度为0的节点加入队列
3. 从队列中取出一个节点，加入排序结果
4. 遍历该节点的所有邻接节点，将其入度减1；若入度变为0，加入队列
5. 重复步骤3-4直到队列为空
6. 若排序结果节点数少于总节点数，说明图中存在环

完整可运行代码

import java.util.*;

/**
 * 拓扑排序实现 - 基于Kahn算法（BFS方式）
 * 同时提供DFS实现方式
 * 时间复杂度: O(V + E)
 * 空间复杂度: O(V + E)
 */
public class TopologicalSort {

    private final int vertices;
    private final List<List<Integer>> adjacencyList;

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

    /**
     * 添加有向边 u -> v
     */
    public void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
    }

    /**
     * Kahn算法 - BFS方式实现拓扑排序
     */
    public List<Integer> kahnSort() {
        int[] inDegree = new int[vertices];

        // 计算每个节点的入度
        for (int u = 0; u < vertices; u++) {
            for (int v : adjacencyList.get(u)) {
                inDegree[v]++;
            }
        }

        // 将所有入度为0的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; 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 : adjacencyList.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

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

        return result;
    }

    /**
     * DFS方式实现拓扑排序
     */
    public List<Integer> dfsSort() {
        boolean[] visited = new boolean[vertices];
        boolean[] onStack = new boolean[vertices]; // 用于检测环
        Deque<Integer> stack = new ArrayDeque<>();

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

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

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

        for (int v : adjacencyList.get(u)) {
            if (!visited[v]) {
                dfsHelper(v, visited, onStack, stack);
            } else if (onStack[v]) {
                throw new RuntimeException("图中存在环，无法进行拓扑排序");
            }
        }

        onStack[u] = false;
        stack.push(u);
    }

    /**
     * 课程选修计划示例 - 检测是否能完成所有课程
     * LeetCode 207: Course Schedule
     */
    public boolean canFinishCourses(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        int[] inDegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            count++;
            for (int v : graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return count == numCourses;
    }

    public static void main(String[] args) {
        // 示例: 任务依赖关系
        // 0 -> 2, 1 -> 2, 2 -> 3, 2 -> 4, 3 -> 5, 4 -> 5
        TopologicalSort graph = new TopologicalSort(6);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        System.out.println("Kahn算法拓扑排序: " + graph.kahnSort());
        System.out.println("DFS算法拓扑排序: " + graph.dfsSort());

        // 课程选修示例
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}};
        System.out.println("能否完成所有课程: " + 
            graph.canFinishCourses(numCourses, prerequisites));
    }
}

关键特性分析

唯一性

拓扑排序的结果通常不唯一。例如，当多个节点同时入度为0时，取出的顺序会影响最终排序。若需要字典序最小的拓扑排序，可将普通队列替换为优先队列（最小堆）。

// 字典序最小拓扑排序
PriorityQueue<Integer> pq = new PriorityQueue<>();
// ... 初始化和处理逻辑相同 ...

环检测

拓扑排序天然支持环检测：若排序结果节点数少于图中总节点数，则图中必存在环。这一特性使拓扑排序成为判断DAG的重要工具。

复杂度分析

其中V为节点数，E为边数。两种算法均需遍历所有节点和边一次。

实际应用场景

• 编译系统：确定源文件的编译顺序，处理头文件依赖
• 任务调度：CPU指令调度、分布式任务编排，确保依赖任务先执行
• 课程规划：判断选修课程的先修关系是否合理
• 数据处理：ETL流程中各阶段的执行顺序编排
• 软件包管理：apt、npm等包管理器的依赖解析

拓扑排序是图论中最实用的算法之一，理解其原理对于处理各类依赖关系问题至关重要。