数据结构与算法 / 系统课时

拓扑排序

拓扑排序

拓扑排序把有向依赖关系转换为满足先后约束的线性序列。本课将用入度法与深度优先搜索处理同一张图,并通过已处理顶点数或 DFS 颜色状态检测依赖环。

学习目标

  • 判断一张有向图是否具备拓扑序列。
  • 使用 Kahn 入度法和 DFS 生成合法拓扑序列。
  • 理解两种方法检测环的条件与复杂度。

问题定义与适用条件

设有向边 u -> v 表示任务 u 必须先于任务 v 完成。拓扑排序要找到一个顶点序列,使每条边的起点都出现在终点之前。只有有向无环图,也就是 DAG,才存在拓扑序列;同一张 DAG 可能有多个正确答案。

课程依赖、构建任务、数据库迁移和工作流编排都可抽象成这一问题。若图中存在依赖环,例如 B -> C -> E -> F -> B,任何顶点都无法成为完整线性顺序中的合法起点,因此必须报告失败,而不是返回部分结果。

两种核心方法

Kahn 入度法先统计每个顶点的入度,把所有入度为 0 的顶点放入队列。每取出一个顶点,就删除它发出的边,并把新变为 0 的顶点加入队列。最终处理数等于顶点数时得到拓扑序列,否则图中存在环。

DFS 方法使用白、灰、黑三种状态:白色表示未访问,灰色表示正在当前递归路径中,黑色表示已经完成。顶点完成时压入栈,最终按栈顺序得到拓扑序列;搜索到灰色顶点说明出现回边,可立即判定存在环。

方法 主要结构 生成顺序的时机 环检测条件
Kahn 入度法 入度数组与零入度队列 顶点出队时加入结果 处理顶点数小于总顶点数
DFS 三色状态与栈 顶点完成时压栈 遇到指向灰色顶点的边

执行过程

下图把零入度队列的变化、DFS 完成顺序和环检测放在同一张依赖图中。阅读时重点观察:入度法不断移除前置约束,DFS 则沿路径深入,并在回溯阶段确定顺序。

入度法与 DFS 拓扑排序流程

完整可运行示例

下面的 Java 17 程序对同一张 DAG 分别执行两种算法,并向副本加入 F -> B,验证 DFS 能识别依赖环。优先队列用于稳定选择字母较小的零入度顶点,因此入度法输出可重复。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;

public class TopologicalSortDemo {

    public static void main(String[] args) {
        List<List<Integer>> graph = createGraph(6);
        addEdge(graph, 0, 2); // A -> C
        addEdge(graph, 1, 2); // B -> C
        addEdge(graph, 1, 3); // B -> D
        addEdge(graph, 2, 4); // C -> E
        addEdge(graph, 3, 5); // D -> F
        addEdge(graph, 4, 5); // E -> F

        System.out.println("入度法拓扑序列: " + format(kahnSort(graph)));
        System.out.println("DFS 拓扑序列: " + format(dfsTopologicalSort(graph)));

        List<List<Integer>> cyclicGraph = copyGraph(graph);
        addEdge(cyclicGraph, 5, 1); // F -> B,形成依赖环
        System.out.println("有环图 DFS 检测: " + hasCycle(cyclicGraph));
    }

    private static List<Integer> kahnSort(List<List<Integer>> graph) {
        int[] indegree = new int[graph.size()];
        for (List<Integer> edges : graph) {
            for (int to : edges) {
                indegree[to]++;
            }
        }

        PriorityQueue<Integer> ready = new PriorityQueue<>();
        for (int vertex = 0; vertex < indegree.length; vertex++) {
            if (indegree[vertex] == 0) {
                ready.offer(vertex);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int current = ready.poll();
            order.add(current);
            for (int next : graph.get(current)) {
                if (--indegree[next] == 0) {
                    ready.offer(next);
                }
            }
        }

        if (order.size() != graph.size()) {
            throw new IllegalStateException("图中存在环,无法生成拓扑序列");
        }
        return order;
    }

    private static List<Integer> dfsTopologicalSort(List<List<Integer>> graph) {
        int[] color = new int[graph.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int vertex = 0; vertex < graph.size(); vertex++) {
            if (color[vertex] == 0 && !dfs(vertex, graph, color, stack)) {
                throw new IllegalStateException("图中存在环,无法生成拓扑序列");
            }
        }
        return new ArrayList<>(stack);
    }

    private static boolean dfs(
            int current,
            List<List<Integer>> graph,
            int[] color,
            Deque<Integer> stack) {
        color[current] = 1;
        for (int next : graph.get(current)) {
            if (color[next] == 1) {
                return false;
            }
            if (color[next] == 0 && !dfs(next, graph, color, stack)) {
                return false;
            }
        }
        color[current] = 2;
        stack.push(current);
        return true;
    }

    private static boolean hasCycle(List<List<Integer>> graph) {
        int[] color = new int[graph.size()];
        for (int vertex = 0; vertex < graph.size(); vertex++) {
            if (color[vertex] == 0 && !dfs(vertex, graph, color, new ArrayDeque<>())) {
                return true;
            }
        }
        return false;
    }

    private static List<List<Integer>> createGraph(int size) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            graph.add(new ArrayList<>());
        }
        return graph;
    }

    private static List<List<Integer>> copyGraph(List<List<Integer>> graph) {
        List<List<Integer>> copy = createGraph(graph.size());
        for (int i = 0; i < graph.size(); i++) {
            copy.get(i).addAll(graph.get(i));
        }
        return copy;
    }

    private static void addEdge(List<List<Integer>> graph, int from, int to) {
        graph.get(from).add(to);
    }

    private static String format(List<Integer> order) {
        List<String> labels = new ArrayList<>();
        for (int vertex : order) {
            labels.add(String.valueOf((char) ('A' + vertex)));
        }
        return String.join(" -> ", labels);
    }
}

将代码保存为 TopologicalSortDemo.java,然后运行:

bash
javac TopologicalSortDemo.java
java TopologicalSortDemo

预期输出

text
入度法拓扑序列: A -> B -> C -> D -> E -> F
DFS 拓扑序列: B -> D -> A -> C -> E -> F
有环图 DFS 检测: true

两条拓扑序列不同但都满足全部边的先后约束,这正说明拓扑序列通常不唯一。

复杂度、Tips 与常见错误

两种方法都会访问每个顶点和每条边一次,时间复杂度为 O(V+E)O(V+E)。使用邻接表时,图、入度数组、颜色数组、队列或栈合计占用 O(V+E)O(V+E) 空间;递归 DFS 还需考虑最坏 O(V)O(V) 的调用栈深度。

  • 需要稳定且可重复的输出时,可用优先队列选择当前编号最小的零入度顶点。
  • Kahn 算法必须在图副本上修改入度,避免污染后续计算使用的原始数据。
  • DFS 不能只用布尔 visited 检测环;必须区分“正在访问”和“已经完成”,否则无法识别回边。
  • 结果少于全部顶点时不得把部分序列当成成功输出,这通常意味着图中存在环。

本课练习

  1. 把示例中的优先队列改为普通队列,记录输出是否变化,并逐条验证所有有向边仍满足先后关系。
  2. 为 Kahn 方法增加环检测演示:向原图加入 F -> B,捕获异常并输出固定错误信息。
  3. 编写验证函数,接收图与候选序列,检查每条边的起点位置是否小于终点位置;合法序列返回 true。

本课总结

  • 拓扑排序只适用于 DAG,结果可能不唯一,但必须满足每条有向边的先后约束。
  • Kahn 方法通过零入度顶点推进,DFS 方法通过完成时间逆序构造结果。
  • 处理数不足或遇到指向灰色顶点的回边,都表示图中存在依赖环。

下一课预告

下一课将学习“强连通分量”,把有向图中能够互相到达的顶点归为同一组,并用两次 DFS 找出这些循环依赖区域。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

拓扑排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通