C++ 实现图的拓扑排序(Kahn 算法)入度统计法及其 BFS 核心源码实现【源码】-C++-PHP中文网

应使用 vector indegree 而非 map，因节点常为整数编号，vector 支持 O(1) 索引且初始化/遍历高效；map 有哈希开销、顺序不可控，且隐式插入会干扰入度统计。

c++ 实现图的拓扑排序(kahn 算法)入度统计法及其 bfs 核心源码实现【源码】

为什么用 `indegree` 数组而不用 `map`？

因为图节点通常用整数编号（0 ~ n-1），indegree 用 vector 直接索引，O(1) 更新、O(n) 初始化；若用 map，每次访问都带哈希开销，且无法保证遍历顺序，BFS 队列依赖稳定入队顺序。实际项目中，哪怕节点是字符串 ID，也应先做离散化映射到整数——否则 indegree["A"]++ 看似简洁，但会隐式插入默认值、干扰统计逻辑。

`queue` 里只放入度为 0 的节点，但为何不能用 `stack`？

Kahn 算法本质是按依赖解除顺序推进，BFS 保证“早解除依赖的节点优先输出”，从而得到合法拓扑序；换成栈就变成 DFS 式回溯，可能提前弹出深层节点，导致后续节点入度未清零就被处理——结果不一定是错的，但不再满足“所有前驱已输出”的拓扑定义。常见错误现象：queue 写成 stack 后，输出序列在有多个入度为 0 起点时顺序混乱，且 result.size() != n 却不报错（因栈不暴露环检测能力）。

必须用 queue（或任何 FIFO 容器），deque 也可，但别用 priority_queue——除非你明确要字典序最小拓扑序
初始化时，遍历所有节点，把 indegree[i] == 0 的 i 入队，别漏掉孤立节点（入度出度均为 0）
每次从队首取节点 u，对其每个邻接点 v 执行 indegree[v]--，仅当 indegree[v] == 0 时才入队

如何用返回值同时表达“成功拓扑序”和“检测到环”？

不要返回 bool 再额外传引用结果，也不要用异常——拓扑排序失败（存在环）是正常业务分支。标准做法是返回 vector：若长度等于节点数，即为有效拓扑序；否则为空或长度不足，表示有环。关键判断点在 BFS 结束后：if (result.size() != n) return {};。容易忽略的是：即使图不连通，只要无环，所有节点仍会被遍历到（因为每个连通分量都有至少一个入度为 0 的起点）；只有环内节点永远无法入队，才会导致 result 缺失。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

vector<int> topologicalSort(int n, const vector<vector>>& graph) {
    vector<int> indegree(n, 0);
    for (int u = 0; u  q;
    for (int i = 0; i  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>{};
}
</int></int></vector></int>

边存储用 `vector>` 还是 `vector>`？

取决于是否需要去重和查重。Kahn 算法中，重复边会导致 indegree[v] 被多次增加，从而让真实入度失真——比如 u → v 出现两次，indegree[v] 变成 2，但删一次 u 后它仍是 1，无法入队，最终误判为环。所以输入边必须先去重，或改用 unordered_set 存邻接表。但注意：unordered_set 迭代无序，不影响算法正确性，但会让结果不唯一；若需稳定输出（如测试比对），应在建图后对每个 graph[u] 调用 sort。