图的遍历: 广度优先遍历和深度优先遍历
上文中我们了解了图的表示, 本节我们来学习图的遍历.
图的遍历是指从图的某一顶点出发, 按照某种搜索方法沿着图的边对图中的所有顶点访问一次且仅访问一次. 广度优先遍历(Breadth-First Search, BFS)和深度优先遍历(Depth-First Search, DFS)是两种常用的图遍历算法.
环境要求
本文所用样例在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)
广度优先遍历(BFS)
基本思想
从图的某一顶点(源点)开始访问, 然后依次访问该顶点的所有未访问过的邻接顶点, 接着再按照这些邻接顶点被访问的先后顺序, 依次访问它们的邻接顶点, 以此类推, 直到图中所有与源点有路径相通的顶点都被访问到. 可以形象地理解为以源点为中心, 一层一层地向外扩展访问.
实现方式
通常使用队列(Queue)来辅助实现. 具体步骤如下:
- 访问起始顶点 v v v, 并将其标记为已访问, 然后将 v v v入队.
- 当队列不为空时, 从队列中取出一个顶点 u u u.
- 遍历顶点 u u u的所有邻接顶点 w w w, 若 w w w未被访问过, 则访问 w w w, 标记 w w w为已访问, 并将 w w w入队.
- 重复步骤 2 和步骤 3, 直到队列为空.
代码实现
之前的例图中图是连通的, 即每一个顶点都能到达其他顶点. 如果图不是连通的, 则需要遍历每一个连通分量, 即从图中的每一个顶点开始, 寻找该顶点所在的连通分量.
因此遍历的代码会尝试从每一个顶点开始, 遍历该顶点所在的连通分量. 参数parent用来记录每个顶点的父节点, 也就是从哪条边到该顶点的. 这是为了方便打印输出.
void visit() {
std::vector<bool> visited(graph_.V()