用C++手搓拓扑排序：从邻接矩阵到完整代码，一个头文件搞定OJ题
用C++手搓拓扑排序：从邻接矩阵到完整代码，一个头文件搞定OJ题
拓扑排序是算法竞赛和数据结构课程中的经典问题，尤其在有向无环图（DAG）的处理中扮演着重要角色。本文将带你从零开始实现一个完整的拓扑排序算法，仅用一个头文件满足OJ平台的苛刻要求，同时深入探讨代码优化和调试技巧。
1. 拓扑排序基础与邻接矩阵表示
拓扑排序的核心思想是将有向图中的顶点排成一个线性序列，使得图中任意一条有向边(u, v)对应的u在序列中总出现在v的前面。这种排序在课程安排、任务调度等场景中有着广泛应用。
邻接矩阵是表示图结构的经典方式。对于一个有n个顶点的图，我们可以用一个n×n的二维数组来表示，其中matrix[i][j]为1表示存在从顶点i到顶点j的边，为0则表示不存在。
// 邻接矩阵示例 int matrix[5][5] = { {0, 1, 0, 1, 1}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} };拓扑排序算法步骤：
- 找出图中入度为0的顶点
- 输出该顶点，并将其从图中删除
- 重复上述过程直到所有顶点都被输出
2. 单头文件限制下的C++实现
OJ平台常常对代码有严格限制，比如只能包含一个头文件。这种情况下，我们需要精心设计代码结构，确保功能完整的同时满足要求。
#include <iostream> using namespace std; class Graph { int **matrix; int vertexCount; bool *visited; // 查找入度为0且未访问的最小顶点 int findZeroInDegreeVertex() { for (int v = 0; v < vertexCount; ++v) { if (visited[v]) continue; bool hasIncomingEdge = false; for (int i = 0; i < vertexCount; ++i) { if (matrix[i][v] != 0) { hasIncomingEdge = true; break; } } if (!hasIncomingEdge) { return v; } } return -1; } public: Graph() { cin >> vertexCount; visited = new bool[vertexCount](); matrix = new int*[vertexCount]; for (int i = 0; i < vertexCount; ++i) { matrix[i] = new int[vertexCount]; for (int j = 0; j < vertexCount; ++j) { cin >> matrix[i][j]; } } } void topologicalSort() { for (int i = 0; i < vertexCount; ++i) { int v = findZeroInDegreeVertex(); if (v == -1) break; // 图中存在环 visited[v] = true; cout << v << " "; // 清除该顶点的所有出边 for (int j = 0; j < vertexCount; ++j) { matrix[v][j] = 0; } } cout << endl; } ~Graph() { delete[] visited; for (int i = 0; i < vertexCount; ++i) { delete[] matrix[i]; } delete[] matrix; } };3. 算法优化与性能分析
上述基础实现的时间复杂度为O(n³)，对于大规模图可能不够高效。我们可以通过预处理入度数组来优化性能。
优化思路：
- 预处理计算每个顶点的初始入度
- 维护一个队列存储当前入度为0的顶点
- 每次处理顶点时，更新其邻接顶点的入度
void optimizedTopologicalSort() { int *inDegree = new int[vertexCount](); // 计算初始入度 for (int i = 0; i < vertexCount; ++i) { for (int j = 0; j < vertexCount; ++j) { if (matrix[i][j] != 0) { inDegree[j]++; } } } for (int i = 0; i < vertexCount; ++i) { int v = -1; // 查找入度为0且未访问的最小顶点 for (int j = 0; j < vertexCount; ++j) { if (!visited[j] && inDegree[j] == 0) { v = j; break; } } if (v == -1) break; // 存在环 visited[v] = true; cout << v << " "; // 更新邻接顶点的入度 for (int j = 0; j < vertexCount; ++j) { if (matrix[v][j] != 0) { inDegree[j]--; } } } cout << endl; delete[] inDegree; }优化后的算法时间复杂度降为O(n²)，更适合处理大规模图。
4. 常见错误与调试技巧
在实现拓扑排序时，开发者常会遇到一些典型问题：
环检测问题：
- 如果图中存在环，拓扑排序将无法完成所有顶点的输出
- 解决方案：在无法找到入度为0的顶点时提前终止并提示
输出顺序问题：
- 当有多个入度为0的顶点时，不同选择会导致不同结果
- OJ通常要求按编号最小优先输出，需要仔细处理
内存管理问题：
- 动态分配的内存需要正确释放
- 在构造函数中分配的资源应在析构函数中释放
调试技巧：
- 使用小规模测试用例验证基本逻辑
- 打印中间状态（如每次迭代后的矩阵和访问数组）
- 对于WA（Wrong Answer），检查边界条件（如空图、单顶点图）
5. C++与C实现的对比
虽然题目允许使用C或C++，但两者在实现上有明显差异：
| 特性 | C++实现 | C实现 |
|---|---|---|
| 内存管理 | 使用new/delete | 使用malloc/free |
| 代码组织 | 可封装为类 | 通常使用结构体和独立函数 |
| 输入输出 | 使用cin/cout | 使用scanf/printf |
| 代码简洁性 | 通常更简洁 | 需要更多样板代码 |
C语言实现示例片段：
struct Graph { int **matrix; int n; int *visited; }; void topologicalSort(struct Graph *g) { // C语言实现类似逻辑 }6. 实战OJ题目解析
让我们分析一个典型OJ题目要求：
输入格式：
- 第一行：测试用例数t
- 每个测试用例：
- 顶点数n
- n×n的邻接矩阵
输出要求：
- 每个测试用例输出一行拓扑序列
- 当有多个选择时，选择编号最小的顶点
关键点处理：
- 严格按照题目要求的输入输出格式
- 注意顶点编号从0开始
- 处理多个测试用例时，确保每个用例独立处理
- 严格遵守头文件限制
int main() { int t; cin >> t; while (t--) { Graph g; g.topologicalSort(); } return 0; }7. 进阶思考与扩展
掌握了基础拓扑排序后，可以进一步探索：
应用场景扩展：
- 课程安排系统
- 任务调度系统
- 依赖关系解析
算法变种：
- 并行拓扑排序
- 加权图的拓扑排序
- 在线拓扑排序（动态图）
性能优化：
- 使用优先队列维护入度为0的顶点
- 稀疏图的邻接表表示
- 并行化计算
相关算法：
- 关键路径算法
- 强连通分量算法
- 欧拉路径算法
在实际编码比赛中，拓扑排序常与其他算法结合使用。例如，在动态规划问题中，我们可能需要按照拓扑顺序处理顶点；在图论问题中，拓扑排序可以帮助我们理解图的结构特性。