农业展示网站模板下载,企业网站建设前网站目的需明确,网站开发人员晋升体系,个人网页设计思路上文中我们了解了图的遍历(DFS/BFS), 本节我们来学习拓扑排序.
在图论中, 拓扑排序(Topological Sorting)是对一个有向无环图(Directed Acyclic Graph, DAG)的所有顶点进行排序的一种算法, 使得如果存在一条从顶点 u 到顶点 v 的有向边 (u, v) , 那么在排序后的序列中, u 一定…上文中我们了解了图的遍历(DFS/BFS), 本节我们来学习拓扑排序.
在图论中, 拓扑排序(Topological Sorting)是对一个有向无环图(Directed Acyclic Graph, DAG)的所有顶点进行排序的一种算法, 使得如果存在一条从顶点 u 到顶点 v 的有向边 (u, v) , 那么在排序后的序列中, u 一定在 v 之前.
环境要求
本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.
Windows: 使用[Visual Studio],Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.关于 Module 的更多信息, 请参考我之前的博客: CMake 构建 C++20 Module 实例(使用 MSVC)
本项目工程目录: 图论代码 适用场景
拓扑排序适用于需要确定一系列任务的执行顺序, 且任务之间存在依赖关系的场景. 下图是是一个示例图, 其中顶点代表任务, 有向边代表依赖(A - B 意味着A 需要在 B 之前完成). 拓扑排序就是给出任务能够完成的先后顺序. 算法实现
常见的拓扑排序算法有两种: Kahn 算法和深度优先搜索(DFS)算法.
Kahn 算法
统计每个顶点的入度(即指向该顶点的边的数量).将所有入度为 0 的顶点加入队列中.从队列中取出一个顶点, 将其输出, 并将该顶点的所有邻接顶点的入度减 1.如果某个邻接顶点的入度变为 0, 则将其加入队列中.重复步骤 3 和 4, 直到队列为空.如果输出的顶点数量小于图中的顶点总数, 则说明图中存在环, 无法进行拓扑排序.过程步骤如图:
起初, 入度为 0 的顶点为 A, F. 我们可以弹出 A 和 F中的任意一个. 这里假设我们先弹出 A. 弹出 A 后, 边线 A - B 和 A - C 被弹出, 并且入度 B 和 C 分别减 1, 此时状态如图所示. 接下来我们要弹出F. 弹出F后, 边线 F - C 被弹出, 并且入度 C 减 1, 此时状态如图所示. 接下来我们弹出B. 弹出B后, 边线 B - D 被弹出, 并且入度 D 减 1, 此时状态如图所示. 接下来我们弹出C. 弹出C后, 边线 C - D 被弹出, 并且入度 D 减 1, 此时状态如图所示. 接下来我们弹出D. 弹出D后, 边线 D - E 被弹出, 并且入度 E 减 1, 此时状态如图所示. 接下来我们弹出E. 弹出E后, 队列为空, 算法结束.代码实现
class TopologicalSortKahn {public:explicit TopologicalSortKahn(const AdjList graph) : graph_(graph) {if (!graph_.Directed()) {throw std::invalid_argument("Graph must be directed for topological sorting.");}}std::vector
