广度优先遍历与最短路径（实战指南）

广度优先遍历与最短路径：从零理解图算法的核心逻辑

你有没有想过，在迷宫中找出口，或者在社交网络中找“最近”的朋友，背后到底用了什么算法？其实，这些看似复杂的场景，都可以用一种高效而优雅的搜索策略来解决——广度优先遍历与最短路径。它不只在算法题中常见，更是实际项目中路径规划、网络路由、推荐系统的重要基石。

如果你刚接触图结构，或者对“最短路径”感到困惑，别担心。这篇文章会带你从零开始，一步步理解广度优先遍历（BFS）是如何找到最短路径的，同时通过真实代码示例，让你真正“看懂”并“用上”它。

什么是图？为什么需要广度优先遍历？

在计算机世界里，图是一种用来表示“关系”的数据结构。比如，城市之间的公路网络、微信好友之间的关注关系、网页之间的超链接，都可以抽象成图。

图由“顶点”（Vertex）和“边”（Edge）组成。顶点代表实体，边代表实体之间的连接。比如 A 城市和 B 城市之间有公路，就有一条从 A 到 B 的边。

在图中，常见的遍历方式有两种：广度优先遍历（BFS）和深度优先遍历（DFS）。我们今天聚焦的是 BFS。

想象你在参加一场“寻宝游戏”，起点是家，终点是宝藏屋。你有三种方式去探索：

• 深度优先：一口气往一条路走到底，万一走错了，回头还得重来；
• 广度优先：先看家周围 100 米内的所有房子，再看 200 米内的，一层一层往外扩散。

显然，BFS 更适合找“最近”的宝藏，因为它按“距离”一层层探索，最先到达目标的路径，就是最短路径。

广度优先遍历的核心思想与执行流程

广度优先遍历的关键在于“层序访问”：从起点出发，先访问所有一步可达的点，再访问所有两步可达的点，依此类推。

我们用一个简单的例子说明：
假设有一个图，顶点是 0 到 5，连接关系如下：

0 — 1 — 2
|   |   |
3 — 4 — 5

起点是 0，我们想用 BFS 找到所有点的访问顺序。

实现的核心是使用一个队列（Queue），先进先出（FIFO）的结构。想象你排队买奶茶，谁先来谁先买。

Python 实现代码示例

from collections import deque

def bfs_traversal(graph, start):
    # visited 用于记录已访问的顶点，避免重复访问
    visited = set()
    # queue 用于存储待访问的顶点，初始加入起点
    queue = deque([start])
    # 用于记录遍历顺序
    traversal_order = []

    while queue:
        # 从队列头部取出一个顶点
        current = queue.popleft()
        
        # 如果该顶点已访问，跳过
        if current in visited:
            continue
            
        # 标记为已访问，并加入遍历顺序
        visited.add(current)
        traversal_order.append(current)

        # 将当前顶点的所有未访问邻居加入队列
        for neighbor in graph[current]:
            if neighbor not in visited:
                queue.append(neighbor)

    return traversal_order

graph = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 4, 5],
    3: [0, 4],
    4: [1, 2, 3, 5],
    5: [2, 4]
}

result = bfs_traversal(graph, 0)
print("广度优先遍历结果:", result)

输出结果：

广度优先遍历结果: [0, 1, 3, 2, 4, 5]

代码逐行解释：

• deque([start])：创建一个双端队列，把起点加入其中。
• queue.popleft()：每次从队列前端取出一个点，保证“先来先处理”。
• visited.add(current)：防止重复访问，是 BFS 的关键。
• for neighbor in graph[current]：遍历当前点的所有邻居。
• if neighbor not in visited：只有未访问的邻居才加入队列，避免死循环。

这个过程就像水波一圈圈扩散，每一轮扩散的范围就是“距离起点的步数”。

广度优先遍历与最短路径的内在联系

在无权图中（即每条边的权重都为 1），广度优先遍历天然能找出从起点到任意点的最短路径。

为什么？因为 BFS 是按“步数”一层层扩展的。当你第一次到达某个点时，那一定是通过最少步数到达的。

比如上面的例子，从 0 到 5：

• 0 → 1 → 4 → 5（3 步）
• 0 → 3 → 4 → 5（3 步）
• 0 → 1 → 2 → 5（3 步）

BFS 会先访问距离为 1 的点（1, 3），再访问距离为 2 的点（2, 4），最后访问距离为 3 的点（5）。所以当 5 第一次被访问时，就是最短路径。

如何记录最短路径？从遍历中还原路径

我们不仅想知道“最短距离”，还想知道“怎么走的”。这就需要记录“前驱节点”（parent）。

Python 实现：记录路径的 BFS

from collections import deque

def bfs_shortest_path(graph, start, target):
    # 记录每个点的前驱节点，用于回溯路径
    parent = {}
    # 记录已访问节点
    visited = set()
    # 队列存储待访问节点
    queue = deque([start])
    visited.add(start)

    while queue:
        current = queue.popleft()

        # 如果找到目标，停止搜索
        if current == target:
            break

        # 遍历所有邻居
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current  # 记录前驱
                queue.append(neighbor)

    # 回溯路径
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent.get(node)  # 获取前驱

    # 反转路径，从起点到终点
    path.reverse()

    # 如果路径长度为1，说明起点就是终点
    if path[0] == start and len(path) == 1:
        return [start]

    return path if path[0] == start else None

graph = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 4, 5],
    3: [0, 4],
    4: [1, 2, 3, 5],
    5: [2, 4]
}

result = bfs_shortest_path(graph, 0, 5)
print("从 0 到 5 的最短路径:", result)

输出结果：

从 0 到 5 的最短路径: [0, 1, 4, 5]

核心逻辑说明：

• parent[neighbor] = current：记录谁把我们“带到”了邻居。
• 回溯时从目标出发，不断找前驱，直到起点。
• 最后反转，得到从起点到终点的路径。

这个技巧在导航系统、游戏 AI、网络路由中非常实用。

实际应用场景：迷宫求解与社交推荐

场景一：迷宫最短路径

假设你有一个 5x5 的迷宫，用 0 表示通路，1 表示墙。你从左上角 (0,0) 出发，想走到右下角 (4,4)。

BFS 可以帮你找到最短路径。只需将每个格子看作一个顶点，上下左右相邻且为通路的格子之间连边。

场景二：社交网络中的“三度好友”

在微信中，A 想认识 C，但 C 不在好友列表。如果 A 和 B 是好友，B 和 C 是好友，那么 A 可以通过 B 认识 C。这本质上就是“距离为 2”的最短路径问题。

BFS 可以快速找出 A 的所有“两度以内”的联系人，实现“推荐好友”功能。

总结：掌握广度优先遍历与最短路径的关键点

广度优先遍历与最短路径，是图算法中最具实用价值的组合之一。它简单、高效，且在无权图中能保证找到最短路径。

• BFS 按层扩展，天然适合找最短路径；
• 使用队列实现，保证“先来先处理”；
• 通过记录前驱节点，可还原路径；
• 适用于迷宫、导航、社交推荐、网络路由等场景。

掌握它，你不仅能解决 LeetCode 的 BFS 题，更能理解真实世界中许多系统的底层逻辑。

如果你现在还觉得“图”很抽象，不妨从一个简单的邻接表开始，手写一次 BFS，再尝试找最短路径。你会发现，原来算法也可以这么“有温度”。

常见问题与注意事项

广度优先遍历与最短路径，不是死板的算法，而是一种思维方式：按距离一层层探索，不走回头路，优先找最近的解。当你在项目中遇到“最快路径”“最近关系”这类问题时，不妨先问问自己：能不能用 BFS 来解决？答案很可能是“能”。