广度优先搜索 BFS 最短路径 图论 Python 40阅读 2025-02-05

广度优先搜索在查找最短路径中的应用

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图数据结构的算法。它从根节点开始，逐层访问相邻节点，直到找到目标节点为止。由于其特性，BFS非常适合用于寻找无权图中两个节点之间的最短路径。

基本概念

图的表示

在计算机科学中，图通常用节点（Vertices）和边（Edges）来表示。一个简单的图可以如下所示：

    A
   / \
  B   C
 / \   \
D   E   F

在这个图中，A是根节点，B、C是A的相邻节点，D、E是B的相邻节点，F是C的相邻节点。

广度优先搜索（BFS）

BFS从起点开始，逐层访问相邻节点。其工作原理如下：

  1. 创建一个队列，并将起始节点加入队列。
  2. 重复以下步骤直到队列为空：
    • 取出队列中的第一个节点。
    • 访问该节点的所有未被访问的邻居节点，并将它们加入队列。

寻找最短路径

由于BFS按层次逐层扩展，因此它会首先找到起点到终点的最短路径。假设我们要在上面的图中寻找从A到F的最短路径，使用BFS可以得到路径为 A -> C -> F。

BFS算法实现

下面是一个简单的Python实现，用于在一个无权图中寻找两个节点之间的最短路径：

from collections import deque, defaultdict

def bfs_shortest_path(graph, start, goal):
    # 创建一个队列，并将起点和初始路径加入队列
    queue = deque([(start, [start])])
    
    # 用于记录已访问的节点，避免重复访问
    visited = set()
    
    while queue:
        (node, path) = queue.popleft()  # 取出队列中的第一个元素
        
        if node not in visited:
            # 标记为已访问
            visited.add(node)
            
            # 检查是否到达目标节点
            if node == goal:
                return path
            
            # 将邻居节点加入队列，并更新路径
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append((neighbor, path + [neighbor]))
    
    return None  # 如果未找到路径，返回None

# 示例图的表示
graph = defaultdict(list)
graph['A'] = ['B', 'C']
graph['B'] = ['D', 'E']
graph['C'] = ['F']
graph['D'] = []
graph['E'] = []
graph['F'] = []

# 寻找从A到F的最短路径
shortest_path = bfs_shortest_path(graph, 'A', 'F')
print("Shortest path from A to F is:", shortest_path)

代码解释

  1. 图的表示：使用defaultdict(list)来存储图中的节点及其邻居。例如，graph['A']包含节点A的所有相邻节点。
  2. 队列初始化：创建一个双端队列deque，并将起始节点和初始路径（只包含起始节点）加入队列。
  3. 访问节点：从队列中取出第一个元素，并检查其是否为目标节点。如果是，则返回路径；否则，将其未被访问的邻居节点加入队列，并更新路径。
  4. 已访问集合：使用set来记录已经访问过的节点，避免重复处理。

应用场景

BFS在许多实际应用中都有广泛的应用，例如：

  • 网络路由算法
  • 游戏中的寻路算法
  • 社交网络分析（如寻找两个人之间的最短联系）

通过本文的介绍和示例代码，希望读者能够理解广度优先搜索的基本原理及其在查找最短路径方面的应用。

📑 目录

📚 相关推荐