了解什么是BFS，宽度优先搜索 (BFS) 解释

计算机科学家经常使用图形来表示数据。图可以表示各种关系，从地图和化合物到社会关系和计算机网络。我们可以对图使用许多算法，例如Dijkstra 算法、深度优先搜索 (DFS)算法和广度优先搜索（或 BFS）算法。虽然您可以使用这两种算法来遍历图的节点，但 BFS 更适合未加权的图。在本文中，我们将探讨 BFS 的工作原理及其应用。

什么是 BFS？

BFS 是一种搜索算法。该算法从源节点开始遍历，然后访问相邻节点。在此之后，算法选择下一个深度级别的最近节点，然后访问下一个未探索的节点，依此类推。由于 BFS 算法在进入下一层之前会访问每一层的节点，这就是“广度优先”这个名称的由来。我们通过跟踪已访问和未访问的节点来确保我们只访问每个节点一次。您可以使用 BFS 来计算路径距离，就像使用 Dijkstra 算法一样。

BFS背后的算法

我们可以用以下伪代码表示基本算法：

BFS（图形，开始）：
    队列 = [开始]
    已访问 = 设置（开始）

    当队列不为空时：
        节点=出队（队列）
        进程（节点）

        对于 graph.neighbors(node) 中的邻居：
            如果邻居不在访问中：
                visited.add（邻居）
                排队（队列，邻居）

在这种情况下，我们将图定义为“graph”，“start”是起始节点。

我们实现了一个队列结构来保存未访问的节点，以及一个“已访问”集来保存已访问的节点。

“while”循环一直持续到队列为空，并开始逐级处理节点。“dequeue”函数在第一个节点被访问时将其从队列中移除。

“处理”功能在节点上执行一些所需的功能，例如更新到其邻居的距离或将数据打印到控制台。

“for”循环遍历当前节点的所有邻居，检查该节点是否已经被访问过。如果不是，则使用“enqueue”函数将其添加到队列中。本质上，每个级别的节点都存储在队列中，并添加它们的邻居以在下一个深度级别访问。这使我们能够确定源节点与图中每个其他节点之间的最短路径。

BFS 的工作

我们将在以下代码示例中使用此图。

解释完基础知识后，是时候看看 BFS 在实践中是如何工作的了。我们将使用具有节点 A、B、C、D、E 和 F 的图形来说明这一点，如图所示。下面的代码展示了如何使用Python 编程语言为这个图实现 BFS 。

从集合导入 defaultdict，双端队列

def bfs（图形，开始）：
    queue = deque([开始])
    已访问 = 设置（[开始]）

    排队时：
        节点 = queue.popleft()
        打印（节点）

        对于图[节点]中的邻居：
            如果邻居不在访问中：
                visited.add（邻居）
                queue.append（邻居）

图=默认字典（列表）
边缘= [（“A”，“B”），“A”，“C”），（“B”，“C”），（“C”，“D”），（“C”，“E” ), ("C", "F"), ("D", "F"), ("E", "F")

对于边中边：
    图[边[0]].append(边[0])
    图[边[1]].append(边[0])

bfs（图，“A”）

守则说明

首先，我们从“collections”模块导入“defaultdict”和“deque”类。这些用于创建具有默认键值的字典，并创建允许添加和删除元素的队列。

接下来，我们使用两个参数“graph”和“start”定义“bfs”函数。我们将“图”参数作为一个字典，其中顶点作为键，相邻顶点作为值。这里，“开始”指的是算法开始的源节点。

“queue = deque([start])”创建一个以源节点为唯一元素的队列，“visited = set([start])”创建一组以源节点为唯一元素的已访问节点。

“while”循环一直持续到队列为空。“node = queue.popleft()”从队列中移除最左边的元素并将其存储在“node”变量中。“print(node)”打印这些节点值。

“for”循环遍历每个邻居节点。“if neighbor not visited”检查邻居是否被访问过。“visited.add(neighbor)”将邻居添加到访问列表，“queue.append(neighbor)”将邻居添加到队列的右端。

在此之后，我们创建一个名为“graph”的默认字典，并定义图的边。“for”循环遍历每条边。“graph[edge[0]].append(edge[1])”将边的第二个元素添加为第一个元素的邻居，并将边的第一个元素添加为第二个元素的邻居。这构建了图形。

最后，我们在“graph”上调用“bfs”函数，源节点为“A”。

代码的实现

这就是 BFS 算法在通过连通图实现和运行时的样子。

在屏幕截图中，我们可以看到输出 [A, B, C, D, EF]。这是我们所期望的，因为 BFS 在移动到下一个深度级别之前探索每个深度级别的节点。回顾图表，我们看到 B 和 C 将被添加到队列中并首先被访问。访问了 B，然后将 A 和 C 添加到队列中。由于已经访问过 A，接下来访问 C，然后删除 A。此后，C 的邻居 D、E 和 F 被添加到队列中。然后访问这些，并打印输出。

对断开连接的图使用 BFS

我们之前将 BFS 用于连通图。但是，当节点未全部连接时，我们也可以使用 BFS。我们将使用相同的图表数据，因为修改后的算法可以用任何一种图表来说明。修改后的代码是：

从集合导入 defaultdict，双端队列

def bfs（图形，开始）：
    queue = deque([开始])
    已访问 = 设置（[开始]）

    排队时：
        节点 = queue.popleft()
        打印（节点）

        对于图[节点]中的邻居：
            如果邻居不在访问中：
                visited.add（邻居）
                queue.append（邻居）

    对于 graph.keys() 中的节点：
        如果节点未被访问：
            queue = deque([节点])
            visited.add（节点）

            排队时：
                节点 = queue.popleft()
                打印（节点）

                对于图[节点]中的邻居：
                    如果邻居不在访问中：
                        visited.add（邻居）
                        queue.append（邻居）


图=默认字典（列表）
边缘= [（“A”，“B”），（“A”，“C”），（“B”，“C”），（“C”，“D”），（“C”，“E "), ("C", "F"), ("D", "F"), ("E", "F")]
对于边中边：
    图[边[0]].append(边[1])
    图[边[1]].append(边[0])

bfs（图，“A”）

我们使用了一个额外的“for”循环。循环使用“graph.keys()”方法遍历所有节点。如果 BFS 找到一个未访问的节点并递归工作，它会启动一个新队列。通过这样做，我们访问了所有断开连接的节点。有关说明，请参见下图。