拓扑排序

概念讲解

什么是拓扑排序？

对有向无环图（DAG）的顶点进行线性排序，使得对于每条边 (u,v)，u 都在 v 前面。

应用

• 任务调度
• 依赖关系
• 判断是否有环

Kahn 算法（BFS）

思路

1. 统计每个点的入度
2. 将入度为 0 的点入队
3. 依次取出，更新邻居入度
4. 入度变为 0 则入队

代码

1234567891011121314151617181920212223vector<int> topoSort(vector<vector<int>>& graph, int n) {
    vector<int> inDegree(n+1, 0);
    for (int u = 1; u <= n; u++) {
        for (int v : graph[u]) inDegree[v]++;
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        for (int v : graph[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }
    
    return result.size() == n ? result : vector<int>();  // 空表示有环
}

时间复杂度：$O(n + m)$

考点分析

初赛考查方式

1. 程序阅读： 拓扑排序
2. 编程题： DAG 相关

常见考点

• 拓扑排序过程
• 判环
• 关键路径

例题精讲

例题 1：拓扑排序

题目： 对 DAG 进行拓扑排序。

解答：

使用 Kahn 算法，结果可能不唯一。

练习题

1. 拓扑排序适用于什么图？

2. 如何判断图是否有环？

1234vector<int> result = topoSort(graph, n);
if (result.size() < n) {
    cout << "有环" << endl;
}

3. 拓扑排序的结果唯一吗？

易错点

⚠️ 注意：

1. 只适用于 DAG
2. 结果可能不唯一
3. 结果数 < n 说明有环
4. 可以用于求关键路径