拓扑排序

发表于 2023-07-18 更新于 2025-08-17 分类于数据结构与算法 Waline：阅读次数：本文字数： 2.6k 阅读时长 ≈ 2 分钟

拓扑排序：处理依赖关系的有序排列算法

拓扑排序（Topological Sort）是针对有向无环图（DAG） 的一种排序算法，其核心是根据节点间的依赖关系，生成一个满足所有前置条件的线性序列。例如在任务调度中，若任务 A 依赖于任务 B，则 A 必须在 B 之后执行，拓扑排序就是生成这样的合法执行顺序。

拓扑排序的核心概念

适用场景

拓扑排序仅适用于有向无环图（DAG），因为若图中存在环（如 A 依赖 B，B 依赖 C，C 依赖 A），则无法确定执行顺序，不存在拓扑排序。

核心目标

对于图中任意一条有向边<u, v>（u 指向 v），在拓扑排序结果中，u 必须排在 v 之前。

例：课程安排中，“数据结构” 是 “算法” 的前置课程，则 “数据结构” 必须排在 “算法” 之前。

拓扑排序的实现算法

拓扑排序的经典实现基于广度优先搜索（BFS），核心思路是反复寻找并移除入度为 0 的节点（无前置依赖的节点），具体步骤如下：

计算入度：统计每个节点的入度（指向该节点的边数）。
初始化队列：将所有入度为 0 的节点加入队列（这些节点可直接执行）。
处理队列：
- 出队一个节点u，加入拓扑排序结果。
- 遍历u的所有邻接节点v，将v的入度减 1（移除u对v的依赖）。
- 若v的入度变为 0，将其入队。
检查结果：若拓扑排序结果包含所有节点，则成功；否则图中存在环，排序失败。

代码实现（Java）

import java.util.*;

public class TopologicalSort {
    // 邻接表存储图
    private Map<String, List<String>> adjList;
    // 节点入度
    private Map<String, Integer> inDegree;

    public TopologicalSort() {
        adjList = new HashMap<>();
        inDegree = new HashMap<>();
    }

    // 添加有向边 u -> v（u是v的前置依赖）
    public void addEdge(String u, String v) {
        // 初始化节点
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        inDegree.putIfAbsent(u, 0);
        inDegree.putIfAbsent(v, 0);

        // 添加边 u -> v
        adjList.get(u).add(v);
        inDegree.put(v, inDegree.get(v) + 1); // v的入度+1
    }

    // 执行拓扑排序
    public List<String> sort() {
        List<String> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();

        // 初始化队列：入度为0的节点
        for (String node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                queue.add(node);
            }
        }

        // 处理队列
        while (!queue.isEmpty()) {
            String u = queue.poll();
            result.add(u);

            // 遍历u的邻接节点v，减少v的入度
            for (String v : adjList.get(u)) {
                inDegree.put(v, inDegree.get(v) - 1);
                if (inDegree.get(v) == 0) {
                    queue.add(v);
                }
            }
        }

        // 若结果包含所有节点，则排序成功；否则存在环
        if (result.size() != inDegree.size()) {
            throw new IllegalArgumentException("图中存在环，无法拓扑排序");
        }
        return result;
    }

    public static void main(String[] args) {
        TopologicalSort graph = new TopologicalSort();
        // 定义任务依赖关系：起床后才能锻炼/刷牙/打包，锻炼后才能洗澡，洗澡后才能穿衣服，刷牙后才能吃早餐
        graph.addEdge("起床", "锻炼");
        graph.addEdge("起床", "刷牙");
        graph.addEdge("起床", "打包午餐");
        graph.addEdge("锻炼", "洗澡");
        graph.addEdge("洗澡", "穿衣服");
        graph.addEdge("刷牙", "吃早餐");

        List<String> order = graph.sort();
        System.out.println("拓扑排序结果（任务执行顺序）：");
        for (String task : order) {
            System.out.println(task);
        }
        // 可能的输出：
        // 起床
        // 打包午餐
        // 锻炼
        // 刷牙
        // 洗澡
        // 吃早餐
        // 穿衣服
    }
}

拓扑排序的应用场景

任务调度
如项目管理中，任务之间存在依赖关系（如 “设计” 完成后才能 “开发”），拓扑排序可生成合法的任务执行顺序。
课程安排
大学课程中，先修课必须在后续课程前完成（如 “高等数学”→“线性代数”），拓扑排序可确定选课顺序。
编译依赖
程序编译时，模块 A 依赖模块 B，则 B 必须先编译，拓扑排序可确定编译顺序（如 Makefile 的依赖处理）。
代码依赖分析
分析代码中函数 / 类的调用关系，拓扑排序可检测循环依赖（如 A 调用 B，B 调用 A）。

总结

拓扑排序是处理依赖关系的核心算法，通过反复移除入度为 0 的节点，生成满足所有前置条件的线性序列。它仅适用于有向无环图，在任务调度、课程安排等场景中不可或缺