Python算法L4:广度优先搜索（详细版）

广度优先搜索（BFS）是图论中的一种基础算法，它以层级遍历的方式逐层展开，保证找到的路径是最短的。在解决实际问题时，BFS因其结构简单且高效，被广泛应用于最短路径搜索、图的遍历、网络抓取、棋盘问题求解等场景。掌握BFS及其应用对于深入理解图论算法和解决复杂问题至关重要。希望这篇文章能帮助你理解BFS的工作原理及其应用场景。如果你有任何疑问或希望进一步探讨，欢迎在评论区留言！

theoxiong

1317人浏览 · 2024-08-28 18:31:11

theoxiong · 2024-08-28 18:31:11 发布

Python广度优先搜索（BFS）详解与应用

广度优先搜索（Breadth-First Search, BFS）是一种常用于图和树结构的遍历算法。它以层级的方式逐层访问节点，确保在进入下一层之前，先访问当前层的所有节点。广度优先搜索的特点使得它在解决诸如最短路径搜索等问题时尤为有效。

BFS算法的基本原理

BFS通过逐层展开的方式遍历图或树。在每一层中，算法会遍历当前节点的所有邻居节点，并在下一层继续这个过程。由于BFS优先访问离起始节点较近的节点，因此它可以保证找到的路径是最短的（对于无权图而言）。

BFS的核心是使用一个队列来维护当前层级的节点，并使用一个集合来记录已经访问过的节点。队列的先进先出（FIFO）特性保证了节点是按层级顺序被处理的。

BFS算法步骤

初始化：将起始节点加入队列，并标记为已访问。
队列循环：在队列不为空的情况下，执行以下步骤：
- 从队列中取出一个节点。
- 访问该节点的所有未被访问的邻居，将这些邻居加入队列，并标记为已访问。
目标检测：如果在遍历过程中找到了目标节点，算法终止，并返回相应路径。
处理结束：如果队列为空且未找到目标节点，表示该图中不存在从起始节点到目标节点的路径。

BFS的Python实现

让我们来看一个具体的BFS实现，假设我们有一个简单的无向图，并希望找到从起始节点到目标节点的最短路径。

from collections import deque

def bfs(graph, start, goal):
    # 初始化队列，并将起始节点添加到队列中
    queue = deque([[start]])
    # 使用一个集合来记录访问过的节点
    visited = set()

    while queue:
        # 取出队列中的第一个路径
        path = queue.popleft()
        # 获取路径的最后一个节点
        node = path[-1]

        # 如果该节点是目标节点，返回路径
        if node == goal:
            return path

        # 如果该节点未被访问过，继续搜索
        if node not in visited:
            # 将该节点标记为已访问
            visited.add(node)
            # 扩展路径并将新的路径加入队列
            for neighbor in graph[node]:
                new_path = list(path)
                new_path.append(neighbor)
                queue.append(new_path)
    
    # 如果找不到路径，返回None
    return None

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 测试BFS函数
start_node = 'A'
goal_node = 'F'
path = bfs(graph, start_node, goal_node)
print(f"从 {start_node} 到 {goal_node} 的最短路径是: {path}")

代码详解

队列初始化：我们使用Python的collections.deque来实现队列。起始节点的路径被首先加入队列。
- queue = deque([[start]])：队列中初始包含一个路径，该路径仅有起始节点。
- visited = set()：使用集合记录已访问节点，避免重复处理。
路径处理与扩展：
- path = queue.popleft()：每次从队列中取出一个路径。popleft()操作保证我们始终处理当前层级的节点。
- node = path[-1]：获取当前路径的最后一个节点，作为扩展的起点。
- if node == goal：检查是否达到了目标节点，若达成则返回路径。
- visited.add(node)：标记该节点已访问，以防止在后续处理中再次访问。
- for neighbor in graph[node]：遍历当前节点的邻居节点，扩展路径并将新路径加入队列。
查找结束的处理：
- 如果在遍历完所有可能路径后仍未找到目标节点，函数返回None。