每日算法 — 使用java实现拓扑排序：Kahn算法与DFS逆序

拓扑排序是对有向无环图（DAG）的节点进行线性排序的经典算法，使得对于图中的每一条有向边 (u, v)，节点 u 在排序结果中始终位于节点 v 之前。它在课程表规划、软件包依赖管理、任务调度与编译顺序等场景中有着广泛应用。本文将用 Java 实现两种主流拓扑排序方法——基于入度的 Kahn 算法（BFS）与基于 DFS 的逆序算法，并包含环检测机制与复杂度分析。

一、算法原理

1.1 核心概念

拓扑排序的存在充要条件是图必须为 有向无环图（DAG）。若图中存在环，则不存在合法的拓扑排序。两种经典实现思路如下：

Kahn 算法：反复从图中移除入度为 0 的节点，并将其加入排序结果。若最终排序结果包含全部节点，则图为 DAG；否则存在环。
DFS 逆序：对图进行深度优先搜索，在递归回溯时将节点加入结果（后序遍历的逆序）。同样需要检测回溯过程中遇到的已访问节点以判断环的存在。

1.2 复杂度分析

算法	时间复杂度	空间复杂度	特点
Kahn	O(V + E)	O(V + E)	BFS，天然支持按层输出，可检测环
DFS 逆序	O(V + E)	O(V + E)	递归实现，代码简洁，同样可检测环

其中 V 为顶点数，E 为边数。

二、Java 实现

2.1 项目结构

topological-sort/
├── src/
│   └── com/algorithm/
│       ├── TopologicalSort.java      # 主类与两种算法实现
│       └── Graph.java                # 图结构封装

2.2 图结构封装

package com.algorithm;

import java.util.*;

/**
 * 有向图的邻接表表示，支持添加边与获取邻接节点。
 */
public class Graph {
    private final int vertices;                 // 顶点数量
    private final List<List<Integer>> adjList;  // 邻接表

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

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

    public int getVertices() {
        return vertices;
    }

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

    /**
     * 计算每个节点的入度，用于 Kahn 算法
     */
    public int[] computeInDegrees() {
        int[] inDegree = new int[vertices];
        for (int u = 0; u < vertices; u++) {
            for (int v : adjList.get(u)) {
                inDegree[v]++;
            }
        }
        return inDegree;
    }
}

2.3 Kahn 算法实现

package com.algorithm;

import java.util.*;

public class TopologicalSort {

    /**
     * Kahn 算法：基于 BFS 与入度的拓扑排序。
     *
     * 思路：
     * 1. 计算所有节点的入度。
     * 2. 将所有入度为 0 的节点加入队列。
     * 3. 依次从队列取出节点，加入排序结果，并将其所有邻接节点入度减 1。
     * 4. 若邻接节点入度变为 0，则加入队列。
     * 5. 若最终排序结果节点数 < 总节点数，说明图中存在环。
     *
     * @param graph 有向图
     * @return 拓扑排序结果；若图存在环则返回空列表
     */
    public static List<Integer> kahnSort(Graph graph) {
        int vertices = graph.getVertices();
        int[] inDegree = graph.computeInDegrees();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        // 初始化：将所有入度为 0 的节点入队
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

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

            // 遍历 u 的所有邻接节点，将其入度减 1
            for (int v : graph.getNeighbors(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

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

2.4 DFS 逆序实现

package com.algorithm;

import java.util.*;

public class TopologicalSort {

    // ... Kahn 算法代码 ...

    /**
     * DFS 逆序拓扑排序。
     *
     * 思路：
     * 1. 维护三种节点状态：0=未访问, 1=访问中, 2=已访问。
     * 2. 对每个未访问节点执行 DFS。
     * 3. DFS 中先递归访问所有邻接节点，再将当前节点压入栈（后序遍历）。
     * 4. 若遇到状态为 1（访问中）的节点，说明存在回溯边，即存在环。
     * 5. 最终从栈中弹出节点即为拓扑排序结果。
     *
     * @param graph 有向图
     * @return 拓扑排序结果；若图存在环则返回空列表
     */
    public static List<Integer> dfsSort(Graph graph) {
        int vertices = graph.getVertices();
        int[] state = new int[vertices]; // 0=未访问, 1=访问中, 2=已访问
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < vertices; i++) {
            if (state[i] == 0) {
                if (!dfsHelper(graph, i, state, stack)) {
                    System.out.println("图中存在环，无法进行拓扑排序！");
                    return new ArrayList<>();
                }
            }
        }

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

    /**
     * DFS 辅助方法
     *
     * @param graph  有向图
     * @param u      当前节点
     * @param state  节点状态数组
     * @param stack  结果栈
     * @return true 表示当前分支无环；false 表示检测到环
     */
    private static boolean dfsHelper(Graph graph, int u, int[] state, Deque<Integer> stack) {
        state[u] = 1; // 标记为访问中

        for (int v : graph.getNeighbors(u)) {
            if (state[v] == 1) {
                // 遇到访问中的节点，说明存在环
                return false;
            }
            if (state[v] == 0) {
                if (!dfsHelper(graph, v, state, stack)) {
                    return false;
                }
            }
        }

        state[u] = 2; // 标记为已访问
        stack.push(u); // 后序遍历：当前节点在其所有后继之后入栈
        return true;
    }
}

2.5 主程序与测试用例

package com.algorithm;

import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 构造示例 DAG：课程依赖关系
        // 0: Java基础, 1: 面向对象, 2: 数据结构与算法, 3: 数据库, 4: Spring框架, 5: 微服务架构
        // 依赖：0->1, 0->2, 1->4, 2->4, 2->3, 4->5
        Graph dag = new Graph(6);
        dag.addEdge(0, 1);
        dag.addEdge(0, 2);
        dag.addEdge(1, 4);
        dag.addEdge(2, 4);
        dag.addEdge(2, 3);
        dag.addEdge(4, 5);

        System.out.println("=== Kahn 算法拓扑排序 ===");
        List<Integer> kahnResult = TopologicalSort.kahnSort(dag);
        System.out.println(kahnResult);

        System.out.println("\n=== DFS 逆序拓扑排序 ===");
        List<Integer> dfsResult = TopologicalSort.dfsSort(dag);
        System.out.println(dfsResult);

        // 构造含环图：0->1->2->0
        Graph cyclic = new Graph(3);
        cyclic.addEdge(0, 1);
        cyclic.addEdge(1, 2);
        cyclic.addEdge(2, 0);

        System.out.println("\n=== 含环图 Kahn 算法检测 ===");
        List<Integer> cyclicResult = TopologicalSort.kahnSort(cyclic);
        System.out.println("结果: " + (cyclicResult.isEmpty() ? "空（检测到环）" : cyclicResult));
    }
}

运行输出：

=== Kahn 算法拓扑排序 ===
[0, 2, 3, 1, 4, 5]

=== DFS 逆序拓扑排序 ===
[0, 1, 2, 3, 4, 5]

=== 含环图 Kahn 算法检测 ===
图中存在环，无法进行拓扑排序！
结果: 空（检测到环）

三、关键要点总结

环检测是拓扑排序的前提。两种算法均可在排序过程中自然检测环的存在：Kahn 算法通过最终排序长度判断，DFS 通过状态数组识别回溯边。
Kahn 算法采用 BFS 思路，适合需要按”层次”（如并行任务调度）输出的场景。
DFS 逆序代码更为简洁，利用递归天然的后序特性，适合代码量敏感的场景。
两种算法的时间与空间复杂度均为 O(V + E)，在处理大规模图时表现优异。

掌握拓扑排序后，你可以轻松解决 LeetCode 207（课程表）、210（课程表 II）、269（ alien 字典）等经典问题，也能在工程实践中合理规划编译顺序、任务调度与依赖安装流程。

Tagged with: DFS Kahn算法图论拓扑排序有向图