进阶数据结构图——拓扑排序（三）

三、拓扑排序3.1 拓扑排序概述拓扑排序(Topological Sort)是一种用于有向无环图(DAG, Directed Acyclic Graph)的排序算法它将图中的所有顶点排成一个线性序列使得对于图中的每一条有向边(u, v)顶点u在这个序列中都出现在顶点v之前。拓扑排序常用于解决依赖关系问题例如任务调度、课程安排、软件包的安装顺序等。算法步骤计算图中所有顶点的入度指向该顶点的边的数量将所有入度为0的顶点加入队列当队列非空时重复以下步骤从队列中取出一个顶点将其加入结果序列对该顶点的所有邻接顶点将其入度减1如果某个邻接顶点的入度变为0则将其加入队列应用场景任务调度确定任务的执行顺序保证依赖任务先执行编译系统确定程序模块的编译顺序课程安排根据课程的先修关系安排学习顺序软件包管理确定软件包的安装顺序电路分析分析数字电路中的信号传播项目管理项目中各活动的依赖关系分析3.2 拓扑排序实现#include iostream #include vector #include queue #include stack #include unordered_map class TopologicalSort { private: // 图的邻接表表示 std::unordered_mapint, std::vectorint graph; // 顶点数 int numVertices; // DFS辅助函数 void dfs(int u, std::vectorbool visited, std::stackint stack) { visited[u] true; for (int v : graph[u]) { if (!visited[v]) { dfs(v, visited, stack); } } // 在回溯时将顶点加入栈中 stack.push(u); } public: TopologicalSort(int vertices) : numVertices(vertices) { // 初始化图 for (int i 0; i vertices; i) { graph[i] std::vectorint(); } } // 添加有向边 void addEdge(int u, int v) { graph[u].push_back(v); } // 使用Kahn算法进行拓扑排序 std::vectorint topologicalSort() { // 计算所有顶点的入度 std::vectorint inDegree(numVertices, 0); for (int u 0; u numVertices; u) { for (int v : graph[u]) { inDegree[v]; } } // 将所有入度为0的顶点加入队列 std::queueint queue; for (int i 0; i numVertices; i) { if (inDegree[i] 0) { queue.push(i); } } // 存储拓扑排序结果 std::vectorint result; // 从队列中取出顶点并更新其邻接顶点的入度 while (!queue.empty()) { int u queue.front(); queue.pop(); result.push_back(u); for (int v : graph[u]) { inDegree[v]--; if (inDegree[v] 0) { queue.push(v); } } } // 检查是否存在环 if (result.size() ! numVertices) { std::cout 图中存在环无法进行拓扑排序 std::endl; return std::vectorint(); } return result; } // 使用DFS实现拓扑排序 std::vectorint topologicalSortDFS() { std::vectorbool visited(numVertices, false); std::stackint stack; // 对所有未访问的顶点进行DFS for (int i 0; i numVertices; i) { if (!visited[i]) { dfs(i, visited, stack); } } // 将栈中的元素依次取出即为拓扑排序结果 std::vectorint result; while (!stack.empty()) { result.push_back(stack.top()); stack.pop(); } return result; } }; int main() { // 创建图 TopologicalSort g(6); g.addEdge(5, 0); g.addEdge(5, 2); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); // 使用Kahn算法进行拓扑排序 std::vectorint result g.topologicalSort(); std::cout Kahn算法拓扑排序结果; for (int v : result) { std::cout v ; } std::cout std::endl; // 使用DFS进行拓扑排序 std::vectorint resultDFS g.topologicalSortDFS(); std::cout DFS算法拓扑排序结果; for (int v : resultDFS) { std::cout v ; } std::cout std::endl; return 0; }