广度优先搜索算法 (BFS)

8.1 BFS算法的工作原理

广度优先搜索 (Breadth-First Search, BFS) —— 是一种在图形中进行遍历或搜索的算法，它从起始顶点开始，先探查当前层的所有相邻顶点，再转到下一层的顶点。

算法步骤：

1. 从选定的起始顶点开始，将其放入队列。
2. 当队列不为空时，执行以下操作：
   • 从队列头部取出顶点，并标记为已访问。
   • 对于每个未访问的相邻顶点，将其加入队列。
3. 重复步骤2，直到访问完起始顶点可到达的所有顶点。

可视化：

时间复杂度：

O(V + E)，其中V是顶点的数量，E是边的数量。

每个节点和每条边在图中只访问一次。

空间复杂度：

O(V)，因为需要使用队列存储顶点，以及用数组存储状态（已访问顶点）。

8.2 使用队列实现BFS

广度优先遍历可以很好地通过队列这种数据结构来实现。

使用队列实现BFS：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 处理节点
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 双向广度优先搜索

BFS在游戏中经常用来找出复杂地形中两点之间的最短路径。这种任务可以很容易地转换为图中两顶点之间的路径搜索问题。这样的图的边是地图上的所有可通过路径。

但为了更快找到路径，通常从两个方向进行搜索。这就用到了双向BFS。

工作原理

双向广度优先搜索 (Bidirectional BFS) 是一种优化的BFS算法，它在起始顶点和目标顶点之间同时进行两个并行遍历。遍历持续进行，直到两次遍历相遇，这大大减少了与经典BFS相比需要检查的顶点和边的数量。

算法步骤：

• 初始化两个队列，一个用于从起始顶点遍历，另一个从目标顶点遍历。
• 初始化两个已访问顶点的集合，用于跟踪两个方向的访问。
• 交替从两个队列进行图遍历。
• 每一步都检查已访问顶点集合是否相交。如果找到相交，路径存在。
• 过程持续进行，直到找到相交节点或队列为空。

时间复杂度

最好情况：O(2 * (V + E)) = O(V + E)，其中V是顶点的数量，E是边的数量。

双向BFS通常比传统的单向BFS遍历更少的顶点，尤其是在大型图中。

空间复杂度：

O(V)，用于存储两个队列和两个已访问顶点的集合。

双向BFS的示例实现

示例很长——这个算法比单向搜索长三倍——所以我不在这里给出。当你真正需要它时，你将能自己编写。

8.4 使用BFS解决的示例问题

使用BFS解决的经典问题示例：

1. 在无向图中搜索最短路径：

BFS用于在无向图中找到从起点到目标的最短路径（最少的边数）。

应用：

• 导航系统中用于找出两点之间的最短路径。
• 网络分析中用于找出数据传输的最短路径。

2. 检查图的连通性：

检查图是否连通，即是否存在任意两顶点之间的路径。

应用：

• 网络分析中用于检查网络的连通性。
• 社交网络分析中用于检查用户组的连通性。

3. 迷宫生成：

使用BFS生成具有特定属性的随机迷宫。

应用：

• 游戏应用中用于创建迷宫。
• 机器人技术中用于测试导航算法。

4. 树中的广度优先搜索：

BFS用于遍历树，以便在每个树层中执行操作（例如打印每层的所有节点）。

应用：

• 数据可视化任务中，需要分层展示数据。
• 规划任务中，需要在层级结构的每个级别执行操作。

5. 检查图的二分图性：

检查图是否为二分图，即是否可以将顶点分成两个集合，使得边仅存在于不同集合的顶点之间。

应用：

• 图论中用于检查图的二分图性。
• 图着色问题中，需要检查是否可以用两种颜色给图着色。