如何用Kahn算法结合BFS核心逻辑改写C语言实现图的拓扑排序的入度统计法？

本文共计619个文字，预计阅读时间需要3分钟。

直接使用 vector。

怎么初始化入度数组和邻接表

节点编号必须从 0 开始连续，否则下标越界或漏统计。假设总节点数为 n：

• vector<int> indegree(n, 0)</int> —— 别用 map 或动态扩容，纯浪费
• vector<vector>> graph(n)</vector> —— 每个 graph[u] 存所有 u → v 的 v
• 遍历每条边 [u, v] 时立刻执行 indegree[v]++ 和 graph[u].push_back(v)

为什么必须用 queue 而不是 stack 或 priority_queue

queue 保证 FIFO，符合“谁先没依赖谁先排”的语义；换成 stack 就退化成 DFS 模拟，失去环检测能力；用 priority_queue 只在需要字典序最小拓扑序时才加，否则徒增 O(log n) 常数开销。

• 初始化队列：只 push 所有 indegree[i] == 0 的 i
• 每次 pop 后，对每个邻接点 v 执行 if (--indegree[v] == 0) q.push(v) —— 减和判必须原子操作
• 别在循环里调用 q.size() 判断是否结束，要用 res.size() 做最终环检测

topo_sort 函数返回空 vector 就代表有环

这是 Kahn 算法最实用的副产物：不需要额外 DFS 判环。只要最终 res.size() != n，就说明存在至少一个节点始终无法入队——它被环锁死了。

立即学习“C++免费学习笔记（深入）”；

• 常见错误现象：queue 提前空了但 res 还没满 —— 直接 return {}，别试图补救
• 不要把 “找不到入度为 0 的起点” 当作图为空，那是环的铁证
• 如果业务要求必须给出部分序（如构建依赖图失败时仍要输出已确定顺序），那就保留 res 并显式报错

真正容易被忽略的是入度更新的时机：必须在遍历 graph[u] 过程中实时减 indegree[v]，而不是先收集再批量处理——后者会导致同一轮内多个节点重复入队，破坏拓扑性。