如何将C语言中图的拓扑排序算法（入度统计法+BFS核心逻辑）改写为长尾词？

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

拓扑排序能成功执行，只有一种情况：

为什么入度统计 + BFS 是最稳妥的实现方式

DFS 实现拓扑排序容易漏掉环检测逻辑，或在回溯时顺序处理不当导致结果错误；而入度统计法天然契合 Kahn 算法本质——每次只选「当前没有前置依赖」的节点。它不依赖递归栈状态，环检测直接体现在最后是否还有剩余入度 > 0 的节点上。

关键点：

• indegree[v] 必须初始化为 0，再遍历所有边进行累加，不能靠 vector 默认值侥幸
• 队列（queue<int>）只推入 indegree[u] == 0 的节点，且入队后立即把 indegree[u] 设为 -1 或用布尔数组标记已访问，避免重复入队
• 每弹出一个节点 u，要遍历其所有邻接点 v，并对每个 v 执行 indegree[v]--；若减后为 0，才入队
• 最终结果长度若小于图中节点总数，说明存在环 —— 这是唯一可靠的环判定依据

代码里最容易写错的三处边界

实际调试时，90% 的失败不是算法逻辑错，而是这些细节没对齐：

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

• 图的节点编号是否从 0 开始？如果输入边是 1-indexed（如 1 2 表示 1→2），但你用 vector<vector<int>> graph(n)，就会越界。务必统一偏移：u--, v--
• graph 邻接表大小必须是 n，不是 n+1（除非你刻意留出 index 0 不用）；否则 graph[u].push_back(v) 可能写到未分配内存
• 当 n == 0 或边集为空时，indegree 数组仍需正确初始化，BFS 队列应把所有入度为 0 的节点（即全部节点）都推进去 —— 否则结果缺失

一个极简可运行的 C++ 版本（含环检测）

以下代码去掉注释后不到 30 行，可直接编译验证：

#include <vector> #include <queue> #include <iostream> using namespace std; vector<int> topological_sort(int n, const vector<vector<int>>& edges) { vector<vector<int>> graph(n); vector<int> indegree(n, 0); for (auto& e : edges) { int u = e[0], v = e[1]; graph[u].push_back(v); indegree[v]++; } queue<int> q; for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i); vector<int> res; while (!q.empty()) { int u = q.front(); q.pop(); res.push_back(u); for (int v : graph[u]) { indegree[v]--; if (indegree[v] == 0) q.push(v); } } return res.size() == n ? res : vector<int>{}; // 有环则返回空 }

调用示例：topological_sort(4, {{0,1},{0,2},{1,3},{2,3}}) 返回 {0,1,2,3}；topological_sort(3, {{0,1},{1,2},{2,0}}) 返回空 vector。

真正难的不是写出这个框架，而是面对一个真实项目里的混合图结构（比如带权重、节点带属性、边来自 JSON 配置）时，能否快速把原始数据映射成干净的 int 节点编号 + 边列表。那个映射过程，往往比排序本身更花时间，也更容易出错。