C++拓扑排序算法详解（从零开始掌握有向无环图的排序方法）

什么是拓扑排序？

拓扑排序（Topological Sort）是将一个有向无环图（DAG）中的所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若存在一条从 u 到 v 的路径，则 u 在序列中出现在 v 的前面。

注意：只有有向无环图（DAG）才能进行拓扑排序。如果图中存在环，则无法完成拓扑排序。

拓扑排序的应用场景

• 课程先修关系（例如：学数据结构前必须先学 C++ 基础）
• 软件包依赖管理（安装 A 前必须先安装 B）
• 任务调度系统（任务 B 必须在任务 A 完成后执行）

实现思路：Kahn 算法

我们使用经典的 Kahn 算法来实现拓扑排序。其核心思想是：

1. 计算每个节点的入度（即有多少条边指向该节点）
2. 将所有入度为 0 的节点加入队列
3. 依次从队列中取出节点，将其加入结果序列，并移除该节点的所有出边（即减少其邻居节点的入度）
4. 若某个邻居节点的入度变为 0，则将其加入队列
5. 重复上述过程，直到队列为空

如果最终结果序列中的节点数等于图中总节点数，则说明图是 DAG，拓扑排序成功；否则，图中存在环。

C++ 拓扑排序算法完整实现

下面是一个完整的 C++ 实现，包含详细注释：

#include <iostream>#include <vector>#include <queue>using namespace std;// 拓扑排序函数vector<int> topologicalSort(int n, vector<vector<int>>& graph) {    // 计算每个节点的入度    vector<int> inDegree(n, 0);    for (int u = 0; u < n; ++u) {        for (int v : graph[u]) {            inDegree[v]++;        }    }    // 将所有入度为0的节点加入队列    queue<int> q;    for (int i = 0; i < n; ++i) {        if (inDegree[i] == 0) {            q.push(i);        }    }    // 存储拓扑排序结果    vector<int> result;    // Kahn 算法主循环    while (!q.empty()) {        int u = q.front();        q.pop();        result.push_back(u);        // 遍历 u 的所有邻居节点        for (int v : graph[u]) {            inDegree[v]--;            if (inDegree[v] == 0) {                q.push(v);            }        }    }    // 如果结果长度不等于节点总数，说明图中有环    if (result.size() != n) {        cout << "图中存在环，无法进行拓扑排序！" << endl;        return {};    }    return result;}int main() {    // 示例：6个节点的有向无环图    int n = 6;    vector<vector<int>> graph(n);    // 添加边：graph[u] 表示从 u 出发的边指向的节点    graph[5].push_back(2);    graph[5].push_back(0);    graph[4].push_back(0);    graph[4].push_back(1);    graph[2].push_back(3);    graph[3].push_back(1);    // 执行拓扑排序    vector<int> order = topologicalSort(n, graph);    if (!order.empty()) {        cout << "拓扑排序结果: ";        for (int node : order) {            cout << node << " ";        }        cout << endl;    }    return 0;}

代码说明

在上面的代码中：

• graph 是邻接表表示的图，graph[u] 存储所有从节点 u 出发能到达的节点。
• inDegree 数组记录每个节点的入度。
• 使用 queue 来存储当前入度为 0 的节点。
• 最后通过比较结果长度与节点总数，判断图中是否存在环。

运行结果示例

对于上述示例图，可能的输出为：

拓扑排序结果: 4 5 0 2 3 1

注意：拓扑排序的结果不唯一，只要满足依赖关系即可。

总结

通过本教程，你已经掌握了如何用 C++ 实现 拓扑排序算法。这项技术是 C++图论算法 中的基础内容，也是解决实际工程问题（如依赖管理）的重要工具。记住，拓扑排序只适用于 有向无环图（DAG），在使用前务必确认图中无环。

希望这篇关于 C++拓扑排序算法 的教程对你有所帮助！动手试试吧，编程能力就是在实践中不断提升的。