图论入门算法:拓扑排序(C++)
上文中我们了解了图的遍历(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<