拓扑排序是有向无环图的一种线性化手段，能够将图中的顶点排成一个序列，使得所有有向边均从前指向后。Kahn算法是最常用的拓扑排序实现方式，它基于入度统计与广度优先搜索，从入度为0的节点开始，不断删除节点及其出边，直到图被清空或发现剩余节点均存在前驱依赖。在C++中，我们可以利用邻接表表示图结构，配合一个记录每个顶点入度的数组和一个先进先出队列完成核心逻辑。这种方法不仅能得到合法拓扑序列，还能顺带检测图中是否存在环。
图结构与入度数组的设计
在C++实现中，首先需要考虑图的存储方式。对于稀疏图，邻接表比邻接矩阵更节省空间。我们可以用vector<vector<int>>来存储每个顶点的后继节点列表，下标代表顶点编号，内部容器存放该顶点直接指向的其他顶点。与此同时，必须单独维护一个vector<int>类型的入度数组indeg，其中indeg[i]表示顶点i当前还有多少条入边未被处理。建图时，每当添加一条从u到v的有向边，就要让indeg[v]增加1。
这样的设计带来两个好处。第一，入度数组让我们在算法初始化阶段就能以O(V)的时间找出所有起点，而不需要遍历整个邻接表去反向查找。第二，在后续删除节点时，只需遍历该节点的出边，将对应终点的入度减1，就能动态反映图的变化。下面给出建图与入度统计的简化代码，展示如何用结构体或函数封装这一过程，避免在主逻辑里混杂过多细节。
#include <iostream>
#include <vector>
using namespace std;
// 图的邻接表与入度数组封装
class Graph {
public:
int n;
vector<vector<int>> adj;
vector<int> indeg;
Graph(int num) : n(num), adj(num), indeg(num, 0) {}
// 添加有向边 u->v
void addEdge(int u, int v) {
adj[u].push_back(v);
indeg[v]++;
}
};
上面的Graph类将顶点数、邻接表和入度数组绑定在一起，构造函数把入度初始化为0。调用addEdge时同步更新入度，保证后续Kahn算法启动时数据处于一致状态。如果图规模很大，这种封装还能方便替换为内存池或文件流式建图，而不影响拓扑主流程。
基于BFS的Kahn核心算法实现
Kahn算法的主体是一个广度优先遍历过程。一开始，把所有入度为0的顶点加入队列，这些顶点没有任何前置依赖，可以立即排入拓扑序列。随后进入循环：每次从队列取出一个顶点u，将其加入结果序列，再遍历u的所有出边u->v，把indeg[v]减1；一旦发现某个v的入度变成0，说明它的所有前驱都已处理完，立即将v入队。如此反复，直到队列为空。
判断算法是否成功的关键在于比较结果序列的长度与图的顶点总数。如果两者相等，说明每个顶点都被顺利剥离，原图是有向无环图，序列即为合法拓扑序；若不等，则剩余顶点全在环上或受环牵连，此时应报错或返回空序列表示无法拓扑排序。下面给出完整的topoSort函数，包含队列操作和环路检测，代码中使用了标准库的queue与vector。
#include <queue>
#include <vector>
// 返回拓扑序列，若检测到环则返回空vector
vector<int> topoSort(const Graph& g) {
queue<int> q;
vector<int> order;
// 初始化：所有入度为0的节点入队
for (int i = 0; i < g.n; i++) {
if (g.indeg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
// 松弛所有出边
for (int v : g.adj[u]) {
g.indeg[v]--;
if (g.indeg[v] == 0) {
q.push(v);
}
}
}
// 环路检测
if (order.size() != g.n) {
return {};
}
return order;
}
上述实现的时间复杂度为O(V+E)，其中V是顶点数、E是边数，因为每个顶点和每条边都只被访问常数次。空间上除了图本身，队列和结果数组最多占用O(V)。在实际工程中，如果顶点编号不连续或规模超内存，可将vector换成unordered_map配合自定义节点对象，但核心的入度减法和零入度入队逻辑保持不变。
完整源码示例与结果验证
为了验证Kahn算法的正确性，我们编写一个包含main函数的完整示例，构造一个简单有向无环图，运行拓扑排序并打印结果。示例图包含顶点0到4，边集为0->1、0->2、1->3、2->3、3->4，显然是一条无环依赖链。运行后应当输出一个以0开头、4结尾的线性序列，且3必在1和2之后。
当我们将边集故意改为含环形式，例如额外添加4->0，程序中的order.size()将小于顶点数，返回空vector，main中可据此提示存在环路。这种自检机制让源码可以直接嵌入构建系统，在编译期依赖分析或任务流水线调度中自动拦截非法配置。以下为可直接编译运行的完整源码。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
int n;
vector<vector<int>> adj;
vector<int> indeg;
Graph(int num) : n(num), adj(num), indeg(num, 0) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
indeg[v]++;
}
};
vector<int> topoSort(Graph& g) {
queue<int> q;
vector<int> order;
for (int i = 0; i < g.n; i++) {
if (g.indeg[i] == 0) q.push(i);
}
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g.adj[u]) {
g.indeg[v]--;
if (g.indeg[v] == 0) q.push(v);
}
}
if (order.size() != g.n) return {};
return order;
}
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 若取消下一行注释则成环，topoSort会返回空
// g.addEdge(4, 0);
vector<int> res = topoSort(g);
if (res.empty()) {
cout << "图中存在环，无法进行拓扑排序" << endl;
} else {
cout << "拓扑序列: ";
for (int x : res) cout << x << " ";
cout << endl;
}
return 0;
}
将这段代码保存为topo.cpp并用g++ topo.cpp -o topo编译，执行后可得拓扑序列。相比手动维护依赖表，用C++实现Kahn入度统计法BFS核心算法既清晰又高效，还能复用入度数组做增量更新。在需要动态增删边的场景里，只需相应修改indeg并重新触发队列补充，即可快速得到新序列，是处理编译依赖、课程排班和流水线任务编排的可靠基础组件。