用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通常要求按编号最小优先输出需要仔细处理内存管理问题动态分配的内存需要正确释放在构造函数中分配的资源应在析构函数中释放调试技巧使用小规模测试用例验证基本逻辑打印中间状态如每次迭代后的矩阵和访问数组对于WAWrong 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每个测试用例顶点数nn×n的邻接矩阵输出要求每个测试用例输出一行拓扑序列当有多个选择时选择编号最小的顶点关键点处理严格按照题目要求的输入输出格式注意顶点编号从0开始处理多个测试用例时确保每个用例独立处理严格遵守头文件限制int main() { int t; cin t; while (t--) { Graph g; g.topologicalSort(); } return 0; }7. 进阶思考与扩展掌握了基础拓扑排序后可以进一步探索应用场景扩展课程安排系统任务调度系统依赖关系解析算法变种并行拓扑排序加权图的拓扑排序在线拓扑排序动态图性能优化使用优先队列维护入度为0的顶点稀疏图的邻接表表示并行化计算相关算法关键路径算法强连通分量算法欧拉路径算法在实际编码比赛中拓扑排序常与其他算法结合使用。例如在动态规划问题中我们可能需要按照拓扑顺序处理顶点在图论问题中拓扑排序可以帮助我们理解图的结构特性。