C++ BFS 代码

什么是 BFS？

广度优先搜索 (BFS) 是一种用于遍历或搜索图的算法。它从给定的顶点开始，探索所有相邻顶点，然后才移动到下一级顶点。BFS 对于查找图中两个顶点之间的最短路径或查找图的连通分量很有用。它也用于拓扑排序，即有向无环图 (DAG) 中顶点的线性排序，使得对于从顶点 u 到顶点 v 的每条边 UV，u 在排序中位于 v 之前。

在本教程中，我们将学习如何在 C++ 中实现 BFS。我们将首先了解 BFS 的概念及其时间复杂度。然后，我们将了解如何使用邻接列表在 C++ 中表示图，以及如何使用 BFS 算法遍历图。

BFS 的概念

BFS 是一种用于遍历或搜索图的算法。它从给定的顶点开始，探索所有相邻顶点，然后才移动到下一级顶点。该算法维护一个要访问的顶点队列，从源顶点开始。每一步，它都会从队列中移除一个顶点，并将其未访问的邻居添加到队列中。这个过程一直持续到队列中没有更多要访问的顶点。

BFS 算法的时间复杂度为 O(V+E)，其中 V 是图中的顶点数，E 是边数。这使得它更适合密集图，其中边数接近顶点数。

在 C++ 中表示图

在 C++ 中有几种表示图的方法。一种常见的表示方法是使用邻接列表，它是与给定顶点相邻的所有顶点的列表。例如，考虑以下具有 5 个顶点的图

我们可以使用邻接列表来表示这个图，如下所示

这里，adj_list[i] 是一个包含顶点 i 的邻居的向量。

在 C++ 中实现 BFS

输出

说明

在此代码中，我们首先定义 bfs() 函数，该函数接受邻接列表 adj_list、起始顶点 start 和可选的目标顶点 target。bfs() 函数初始化一个布尔数组 visited 以跟踪已访问的顶点，以及一个向量 order 以存储 BFS 遍历顺序。它还创建一个队列 q 来保存要访问的顶点。

然后，该函数将起始顶点添加到队列中并将其标记为已访问。然后它进入一个循环，该循环一直持续到队列为空。循环的每次迭代都会从队列中移除下一个顶点并将其添加到遍历顺序中。然后它将其所有未访问的邻居添加到队列中并将其标记为已访问。

最后，如果指定了目标顶点但未找到，则函数返回一个空向量。否则，它返回遍历顺序。

在 main() 函数中，我们为具有 5 个顶点的图创建了一个邻接列表。然后我们从顶点 0 开始执行 BFS 搜索，并将遍历顺序存储在 order 向量中。最后，我们将遍历顺序打印到控制台。