C++ 实现图的拓扑排序：原理、算法与代码示例

拓扑排序的核心概念

拓扑排序是针对有向图的一种顶点线性排序方法。一个合法的拓扑序列必须满足两个条件：首先，图中的每个顶点在序列中仅出现一次；其次，若图中存在从顶点 x 到顶点 y 的有向边，则在该序列中 x 必须出现在 y 之前。因此，拓扑排序仅适用于有向无环图（DAG）。如果图中存在环路，则无法找到有效的拓扑序。

理解拓扑排序的关键在于“入度”与“出度”。入度指指向当前节点的边的数量，即有多少条边指向自己；出度指从当前节点发出的边的数量，即有多少条边从自己指出。拓扑排序的本质就是不断寻找入度为 0 的节点，将其加入序列后“移除”，从而降低其 successor 节点的入度，直至所有节点都被排序。

Kahn 算法流程与逻辑

Kahn 算法是实现拓扑排序最直观的方法，主要依赖队列来执行。算法的执行步骤如下：

1. 初始化：计算图中所有节点的入度，并将所有入度为 0 的节点加入队列。
2. 循环处理：只要队列不为空，就取出队首节点 t，将其加入拓扑序列。随后，遍历以 t 为起点的的所有边，将 t 指向的节点 j 的入度减 1。如果节点 j 的入度变为 0，则将 j 加入队列。
3. 结束判断：当队列空时，检查输出的顶点数是否等于图中总顶点数 n。若小于 n，说明图中存在回路，无法拓扑排序；否则，输出的序列即为一个拓扑序（注意：拓扑序可能不唯一）。

该算法的时间复杂度为 O(n + m)，其中 n 为点数，m 为边数，主要耗时在于遍历所有节点和边。

C++ 代码实现

在实际编程或算法竞赛中，通常使用邻接表来存储稀疏图，并利用数组模拟链表以提高效率。以下提供两种常见的 C++ 实现方式。

第1步：基础模板实现（STL queue）

这是最标准的实现方式，逻辑清晰，易于理解。首先定义图的存储结构（邻接表），并维护一个入度数组 in[]。

#include <iostream>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx; // 邻接表头指针、边值、下一个节点索引、下标
int in[N]; // 入度数组
int n, m;

void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

bool topsort() {
    queue<int> q;
    // 1. 将所有入度为 0 的点加入队列
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0)
            q.push(i);
    }

    int cnt = 0; // 记录拓扑序列中节点的个数
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        cnt++; // 找到一个入度为0的点，计数加1

        // 2. 删除从t出发的所有边，即减小后继节点的入度
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            in[j]--; // 入度减1
            if (in[j] == 0) {
                q.push(j); // 如果入度变为0，加入队列
            }
        }
    }
    return cnt == n; // 如果处理的节点数等于总节点数，则无环
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h); // 初始化邻接表头指针
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        in[b]++; // 记录b的入度增加
    }

    if (topsort()) {
        cout << "Topological sort exists." << endl;
        // 若要输出具体序列，可在topsot过程中记录
    } else {
        cout << "-1" << endl; // 存在环
    }
    return 0;
}

第2步：数组模拟队列优化实现

对于数据规模较大或对性能有严格要求的场景，可以使用数组模拟队列以减少 STL 容器的开销。这种方法通常配合静态分配的 top[] 数组直接存储结果。

// 假设全局变量 h, e, ne, idx, in[], n 已定义
// top[] 用于存储拓扑序列
bool topsort_optimized() {
    int hh = 0, tt = -1; // 队头和队尾指针
    
    // 1. 初始化队列：放入所有入度为0的点
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            top[++tt] = i;
        }
    }
    
    while (hh <= tt) {
        int t = top[hh++]; // 取出队头元素
        
        // 2. 遍历 t 的出边，更新后继节点入度
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            in[j]--; // 入度减1
            if (in[j] == 0) {
                top[++tt] = j; // 入度为0，加入队列末尾
            }
        }
    }
    
    // 如果所有点都入队了（tt == n-1，因为从0开始编号存储且总数为n），说明无环
    return tt == n - 1;
}

应用场景与注意事项

• 任务调度：在有依赖关系的任务系统中（如编译项目、课程选修），拓扑排序可用于确定任务的执行顺序。例如，必修课必须在选修课之前完成。
• 环检测：如果拓扑排序结束后输出的节点数少于图的总节点数，说明图中存在环，这在死锁检测或版本冲突检查中非常有用。
• 重边与自环：上述代码标准实现中，邻接表天然支持重边处理（每条边独立记录），但自环会导致该节点入度永远无法降为 0，从而被正确识别为环。

总结

C++ 实现图的拓扑排序主要依赖 Kahn 算法，核心在于维护节点入度和队列操作。通过邻接表存储图结构，可以高效地遍历和处理边关系。掌握数组模拟队列与 STL 库的两种写法，能够应对不同场景下的性能需求。以上就是 C++ 详细讲解图的拓扑排序的详细内容，更多关于 C++ 图算法的资料请关注本站其它相关文章！