Python 中的广度优先搜索

在 Python 中，广度优先搜索和深度优先搜索技术被用来搜索树或图。这两者都是每个 Python 初学者必须掌握的最重要的话题。我们将深入探讨 Python 中的广度优先搜索是什么，它的算法如何工作，如何在 Python 中实现它（附有示例代码），以及结果。我们还将学习 BFS 的实际应用以及广度优先搜索的用途。

什么是广度优先搜索？

正如前面提到的，广度优先搜索 (BFS) 是一种搜索图或树的方法。遍历树意味着访问每个节点。广度优先搜索是一种递归方法，用于搜索树或图的所有节点。在 Python 中，我们可以利用列表或元组等数据结构来执行 BFS。在树和图中，广度优先搜索几乎是相同的。唯一的区别是树可能存在循环，这会使我们能够重新访问同一个节点。

BFS 算法

在学习编写 Python 代码之前，让我们先回顾一下广度优先搜索所使用的方法论，并讨论其输出。以魔方（Rubik's Cube）为例。魔方被认为是寻找一种方法，将其从杂乱的颜色变成单一的颜色。将魔方与树或图进行比较，我们可以得出结论，魔方的潜在状态对应于我们网络的顶点，而魔方的潜在动作对应于图的边。

BFS 算法遵循下面讨论的步骤。

1. 首先，将我们图的任意一个顶点放在队列的底部。
2. 将创建队列中的第一个元素添加到已检查对象的列表中。
3. 创建一个列表，包含所有看起来与该顶点相邻的节点。不在已访问列表中的单个节点将被移到队列的末尾。
4. 重复上述两个步骤，即步骤 2 和 3，直到队列为空。

由于广度优先搜索扫描给定图的每个节点，标准的 BFS 算法将树或图的每个节点或顶点分成两个不同的组。

• 已访问
• 未访问

所述技术的目标是访问每个顶点，同时避免重复的循环。BFS 从单个节点开始，然后检查距离为一的所有节点，接着是距离为二的所有其他节点，以此类推。为了保留待访问的节点，BFS 需要一个队列（或在 Python 中，一个列表）。

代码

输出

The Breadth First Search Traversal for The Graph is as Follows: 
3 1 

在上面所示的 Python 程序中，我们首先生成了图，我们在此图上应用了广度优先搜索方法。之后，我们初始化了两个列表：一个用于跟踪 BFS 算法已访问的图节点，另一个用于跟踪队列中的节点。

我们已声明一个函数，其参数为已访问节点、图本身以及按照上述步骤进行的下一个节点。我们需要在函数内不断地添加 visited_vertices 和 queue 列表。

然后程序将对待访问节点队列执行 while 循环，并在访问当前节点后将其移除并显示。最后，我们使用 for 循环查找未访问的节点，然后将它们添加到 visited_vertices 和 queue 列表中。然后，我们使用我们想要在输出中看到的第一个节点作为参数调用 BFSearch 函数。

时间复杂度

广度优先搜索算法的时间复杂度为 O(V+E)，其中 V 代表顶点的数量，E 代表边的数量。此外，BFS 算法的空间复杂度为 O(V)。

广度优先遍历的应用

• 最短路径与最小范围：无权图的树。无权图中的最短路径是具有最少边的路径。当使用广度优先时，我们通常使用最少的边从源节点到达目标节点。点对点 (P2P) 网络。BFS 通常用于发现点对点网络（如 BitTorrent）中的所有相邻顶点。
• 搜索引擎中的爬虫：爬虫通过从广度到深度的方式创建索引。目标是从根页面开始，然后探索该页面上的所有链接。
• 社交网站：我们可以使用广度优先搜索来识别社交连接中与某个成员距离为 'm' 的人，最多可达 'm' 层。
• 在 GPS 导航设备中，使用广度优先搜索找到所有附近的站点。
• 在网络中，广播的数据包使用广度优先搜索算法来触达所有节点。
• 在垃圾收集领域， Cheney 的算法使用广度优先搜索来复制垃圾回收。
• 无向网络中的循环识别可以通过广度优先搜索或 DFS（深度优先搜索）来完成。有向网络中的循环也可以使用 BFS 来找到。
• Ford-Fulkerson 算法：为了在 Ford-Fulkerson 方法中确定最佳流，我们可以使用广度优先或深度优先遍历。更优选使用广度优先遍历，因为它将最坏情况时间复杂度降低到 O (VE²)。发现我们的路径，即判断两个节点之间是否存在路径，我们可以使用广度优先或深度优先遍历。