拓扑排序算法通过入度统计、BFS遍历和环检测三步完成：先统计各顶点入度并将入度为0者入队；再逐个出队并更新邻接点入度；最后检查结果长度是否等于顶点数以判定是否存在环。

一、入度统计与队列初始化

该步骤通过遍历所有边，统计每个顶点的入度，并将所有入度为0的顶点加入队列，作为拓扑排序的起始候选节点。入度为0表示该节点不依赖任何其他节点，可优先处理。

1、声明一个大小为顶点数的数组inDegree，初始化为0。

2、遍历图的邻接表或边集，对每条边u→v，执行inDegree[v]++。

3、创建一个队列q，遍历所有顶点i，若inDegree[i] == 0，则将i入队。

二、BFS主循环与拓扑序列构建

在队列非空时持续出队，将当前顶点加入结果序列，并对其所有邻接顶点的入度减1；若某邻接顶点入度减至0，则将其入队。该过程模拟有向无环图中依赖关系的逐层释放。

1、声明一个vector result用于存储拓扑序。

2、当队列q不为空时，执行循环体：

3、取出队首顶点u，将u压入result。

4、遍历u的所有邻接顶点v：

5、执行inDegree[v]--。

6、若inDegree[v] == 0，则将v入队。

三、环检测与有效性验证

拓扑排序成功当且仅当最终结果序列长度等于图中顶点总数。若存在环，则至少有一个顶点的入度始终无法归零，导致其无法入队，结果序列长度将小于顶点数。

C++14

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

下载

1、循环结束后，检查result.size()是否等于顶点总数n。

2、若相等，说明图中不存在有向环，result即为合法拓扑序。

3、若不等，说明图中存在至少一个有向环，拓扑排序失败。

四、邻接表结构定义与图输入适配

使用vector>表示邻接表，索引为源顶点，内部vector存储所有直接后继顶点。该结构支持O(1)访问出边，便于在BFS中高效遍历邻接点。

1、声明adj为vector>(n)，其中n为顶点数量。

2、对每条有向边(u, v)，执行adj[u].push_back(v)。

3、确保顶点编号为0至n−1的连续整数，避免下标越界。

五、完整函数封装与返回设计

将上述逻辑封装为独立函数，接收邻接表和顶点数，返回vector类型的结果序列。函数不输出任何内容，不调用print，仅完成计算与判定，符合模块化接口规范。

1、函数签名定义为vector topologicalSort(const vector>& adj, int n)。

2、在函数内完成inDegree数组分配、队列初始化、BFS执行及长度校验。

3、若检测到环，返回空vector，调用方需检查size()以判别有效性。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！