拓扑排序是针对有向无环图的一种线性排序算法，最终得到的序列中，对于任意一条有向边u->v，顶点u都会出现在顶点v之前。该算法只能应用于有向无环图，如果图中存在环，则无法得到合法的拓扑序列。
拓扑排序的核心原理
常用的拓扑排序实现方式是Kahn算法，核心思路基于顶点的入度概念：入度指的是指向该顶点的有向边的数量。算法的基本流程如下：
- 统计图中所有顶点的入度，将入度为0的顶点加入队列
- 从队列中取出一个顶点，将其加入拓扑序列
- 遍历该顶点的所有出边，将对应终点的入度减1，如果终点的入度变为0，将其加入队列
- 重复上述步骤，直到队列为空
- 如果最终拓扑序列的长度等于图的顶点总数，说明图中无环，序列合法；否则图中存在环，无法完成拓扑排序
C++实现拓扑排序的完整代码
下面的代码实现了基于邻接表存储的有向无环图的拓扑排序，使用Kahn算法完成排序逻辑：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序函数，参数分别为顶点数量、邻接表，返回拓扑序列，若为空则说明有环
vector<int> topologicalSort(int n, const vector<vector<int>>& adj) {
vector<int> inDegree(n, 0);
// 统计每个顶点的入度
for (int u = 0; u < n; u++) {
for (int v : adj[u]) {
inDegree[v]++;
}
}
queue<int> q;
// 将入度为0的顶点加入队列
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
vector<int> topoOrder;
while (!q.empty()) {
int u = q.front();
q.pop();
topoOrder.push_back(u);
// 遍历当前顶点的所有出边
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// 判断是否存在环
if (topoOrder.size() != n) {
return {};
}
return topoOrder;
}
int main() {
// 示例：4个顶点的有向无环图
int n = 4;
vector<vector<int>> adj(n);
// 添加边：0->1, 0->2, 1->3, 2->3
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[2].push_back(3);
vector<int> result = topologicalSort(n, adj);
if (result.empty()) {
cout << "图中存在环，无法进行拓扑排序" << endl;
} else {
cout << "拓扑排序结果：";
for (int v : result) {
cout << v << " ";
}
cout << endl;
}
return 0;
}
代码说明与复杂度分析
上述代码中使用vector<vector<int>>存储邻接表，适合表示稀疏图，节省存储空间。入度统计阶段需要遍历所有边，时间复杂度为O(V+E)，其中V是顶点数，E是边数。队列操作每个顶点和边最多处理一次，整体时间复杂度为O(V+E)，空间复杂度为O(V)用于存储入度数组、队列和拓扑序列。
常见问题与注意事项
- 如果图中存在环，拓扑序列的长度会小于顶点总数，需要在代码中做对应判断
- 入度为0的顶点可能有多个，队列取出的顺序不同，最终得到的拓扑序列也可能不同，这些都是合法结果
- 如果图是有向有环图，需要先处理环的问题，否则无法得到有效的拓扑排序结果
- 邻接表存储方式比邻接矩阵更适合顶点数较多的场景，避免不必要的空间浪费