C++实现拓扑排序详解（小白也能学会的图论算法）

例如，在选修课程时，某些课程有先修要求（如“数据结构”必须在“算法设计”之前学习），这些依赖关系可以用DAG表示，而拓扑排序就能给出一个合法的学习顺序。

拓扑排序的两种常见实现方法

在C++中，我们通常使用以下两种方法实现拓扑排序：

• Kahn 算法（基于入度）
• DFS 深度优先搜索法

本文将重点讲解更直观、易于理解的 Kahn 算法。

Kahn 算法原理

Kahn 算法的核心思想是：

1. 计算每个顶点的入度（即有多少条边指向该顶点）。
2. 将所有入度为0的顶点加入队列。
3. 从队列中取出一个顶点，加入结果列表，并将其所有邻接顶点的入度减1。
4. 如果某个邻接顶点的入度变为0，则将其加入队列。
5. 重复步骤3-4，直到队列为空。

如果最终结果列表中的顶点数等于图中总顶点数，则说明图是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);            }        }    }    // 如果结果包含所有节点，说明是DAG；否则存在环    if (result.size() != n) {        cout << "图中存在环，无法进行拓扑排序！" << endl;        return {};    }    return result;}int main() {    // 示例：5个节点的有向图    int n = 5;    vector<vector<int>> graph(n);    // 添加边：0→1, 0→2, 1→3, 2→3, 3→4    graph[0].push_back(1);    graph[0].push_back(2);    graph[1].push_back(3);    graph[2].push_back(3);    graph[3].push_back(4);    vector<int> order = topologicalSort(n, graph);    if (!order.empty()) {        cout << "拓扑排序结果: ";        for (int node : order) {            cout << node << " ";        }        cout << endl;    }    return 0;}

运行结果与解释

以上代码输出：

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

这表示一种合法的任务执行顺序。注意：拓扑排序的结果可能不唯一，只要满足依赖关系即可。

应用场景

C++图论算法中的拓扑排序在实际开发中有广泛应用：

• Makefile 编译依赖分析
• 课程先修关系安排
• 软件包依赖安装顺序
• 项目任务调度（如 PERT 图）

总结

通过本教程，你已经掌握了 有向无环图拓扑排序的基本原理和 C++ 实现方法。Kahn 算法逻辑清晰、易于编码，是解决依赖排序问题的利器。记住：只有 DAG 才能进行拓扑排序，若图中存在环，则无法得到合法的排序结果。

希望这篇关于 拓扑排序算法 的教程对你有所帮助！动手实践一下吧，试着修改图的结构，观察不同的排序结果。