【数据结构与算法-Day 32】掌握广度优先搜索 (BFS)，轻松解决无权图最短路径问题

大模型铲屎官

1124人浏览 · 2025-09-24 09:00:00

大模型铲屎官 · 2025-09-24 09:00:00 发布

Langchain系列文章目录

01-玩转LangChain：从模型调用到Prompt模板与输出解析的完整指南
 02-玩转 LangChain Memory 模块：四种记忆类型详解及应用场景全覆盖
 03-全面掌握 LangChain：从核心链条构建到动态任务分配的实战指南
 04-玩转 LangChain：从文档加载到高效问答系统构建的全程实战
 05-玩转 LangChain：深度评估问答系统的三种高效方法（示例生成、手动评估与LLM辅助评估）
06-从 0 到 1 掌握 LangChain Agents：自定义工具 + LLM 打造智能工作流！
07-【深度解析】从GPT-1到GPT-4：ChatGPT背后的核心原理全揭秘
 08-【万字长文】MCP深度解析：打通AI与世界的“USB-C”，模型上下文协议原理、实践与未来

数据结构与算法系列文章目录

文章目录

Langchain系列文章目录
Python系列文章目录
PyTorch系列文章目录
机器学习系列文章目录
深度学习系列文章目录
Java系列文章目录
JavaScript系列文章目录
Python系列文章目录
Go语言系列文章目录
Docker系列文章目录
数据结构与算法系列文章目录
摘要
一、回顾：图的遍历
- - 1.1 什么是图的遍历？
  - 1.2 回顾深度优先搜索 (DFS)
二、广度优先搜索 (BFS) 的核心思想
- - 2.1 “地毯式”搜索的直观理解
  - 2.2 BFS 的工作伙伴：队列 (Queue)
三、BFS 算法原理与流程详解
四、BFS 的代码实现 (以 Java 为例)
五、BFS 的应用场景
六、BFS 与 DFS 的全方位对比
七、总结

摘要

欢迎来到「数据结构与算法」系列的第 32 篇。在上一篇文章中，我们深入探讨了图的深度优先搜索（DFS），它像一个执着的探险家，沿着一条路走到黑再回头。今天，我们将学习图的另一种核心遍历策略——广度优先搜索（Breadth-First Search, BFS）。BFS 如同水波扩散，从起点开始，一层一层地向外探索，直到覆盖所有可达的顶点。这种“地毯式”的搜索机制，使其在解决特定问题，尤其是无权图的最短路径问题上，具有无可比拟的优势。本文将通过图解、代码实战和场景分析，带你彻底掌握 BFS 的原理与应用。

一、回顾：图的遍历

1.1 什么是图的遍历？

图的遍历（Graph Traversal）是指从图中的任意一个顶点出发，系统地访问图中所有顶点，且每个顶点仅被访问一次的过程。这是所有图算法的基础，无论是寻找路径、检查连通性还是构建生成树，都离不开遍历操作。

1.2 回顾深度优先搜索 (DFS)

在上一篇文章中，我们学习了深度优先搜索（DFS）。其核心思想是“不撞南墙不回头”。它从一个顶点开始，尽可能深地探索图的分支。当一个顶点的所有邻接点都已被访问，DFS 就会回溯到上一个顶点，继续探索其他未被访问的分支。这个过程通常借助栈（Stack）或递归来实现。

（图源网络，左为 DFS，右为 BFS）

与 DFS 的“纵向”深入不同，BFS 采用的是一种“横向”扩展的策略。

二、广度优先搜索 (BFS) 的核心思想

2.1 “地毯式”搜索的直观理解

想象一下，向平静的湖面投下一颗石子，水波会从中心点开始，一圈一圈地向外均匀扩散。广度优先搜索（BFS）的模式与此非常相似。

起点：就是投下石子的中心点。
第一层：与起点直接相连的所有顶点，如同第一圈水波。
第二层：与第一层顶点相连，但尚未被访问过的所有顶点，如同第二圈水波。
以此类推…

BFS 总是先访问完离起点最近的（距离为 k）所有顶点，然后才会去访问距离为 k+1 的顶点。这种逐层推进、步调一致的特性是 BFS 的精髓。

2.2 BFS 的工作伙伴：队列 (Queue)

要实现这种“先来先服务”的逐层搜索，哪种数据结构最合适呢？答案是队列（Queue）。

队列遵循**先进先出（First-In, First-Out, FIFO）**的原则，完美契合了 BFS 的需求：

保存待访问节点：我们将待访问的顶点放入队列中。
保证访问顺序：最先被发现的顶点（离起点近）会最先被放入队列，因此也最先被取出并处理其邻居。这确保了搜索是逐层进行的。

与此形成鲜明对比的是，DFS 使用栈（后进先出），导致其总是优先处理最新发现的节点，从而实现“一条路走到黑”的深入探索。

三、BFS 算法原理与流程详解

3.1 算法步骤拆解

BFS 算法的执行流程非常清晰，可以归纳为以下几个步骤：

初始化：
- 创建一个队列 Q，用于存放待访问的顶点。
- 创建一个集合 visited（通常用布尔数组或哈希集实现），用于记录已经访问过的顶点，防止重复访问和陷入死循环。
- 选择一个起始顶点 s，将其加入队列 Q，并标记为已访问 visited[s] = true。
循环处理：当队列 Q 不为空时，执行以下循环：
- 出队：从队列头部取出一个顶点 u。
- 处理：可以对顶点 u 进行相关操作（例如打印）。
- 邻居入队：遍历 u 的所有邻接顶点 v：
  - 如果 v 尚未被访问（visited[v] == false）：
    - 将 v 标记为已访问（visited[v] = true）。
    - 将 v 加入队列 Q 的尾部。
结束：当队列 Q 为空时，表示从起始顶点 s 出发所有可达的顶点均已访问完毕，遍历结束。

3.2 可视化图解 BFS 过程

（1）准备工作：一个示例图与一个空队列

让我们用一个具体的无向图来演示 BFS 的过程。假设我们从顶点 A 开始遍历。

初始状态:

队列 Q: []
已访问集合 visited: {}
输出结果: ""

（2）步骤演练

Step 1:

选择起始点 A。将 A 入队，并标记为已访问。
队列 Q: [A]
已访问 visited: {A}
输出结果: ""

Step 2:

A 出队。处理 A（打印）。
将 A 的所有未访问邻居 B, C, D 依次入队，并标记为已访问。
队列 Q: [B, C, D]
已访问 visited: {A, B, C, D}
输出结果: "A"

Step 3:

B 出队。处理 B（打印）。
将 B 的未访问邻居 E 入队，并标记为已访问。
队列 Q: [C, D, E]
已访问 visited: {A, B, C, D, E}
输出结果: "A, B"

Step 4:

C 出队。处理 C（打印）。
将 C 的未访问邻居 F, G 依次入队，并标记为已访问。
队列 Q: [D, E, F, G]
已访问 visited: {A, B, C, D, E, F, G}
输出结果: "A, B, C"

Step 5:

D 出队。处理 D（打印）。
将 D 的未访问邻居 H 入队，并标记为已访问。
队列 Q: [E, F, G, H]
已访问 visited: {A, B, C, D, E, F, G, H}
输出结果: "A, B, C, D"

Step 6:

E 出队。处理 E（打印）。
E 的邻居 B 和 H 都已被访问，无操作。
队列 Q: [F, G, H]
已访问 visited: {A, B, C, D, E, F, G, H}
输出结果: "A, B, C, D, E"

Step 7, 8, 9:

依次将 F, G, H 出队并打印。它们的邻居都已被访问。
最终队列变为空，遍历结束。

最终遍历顺序: A -> B -> C -> D -> E -> F -> G -> H。
可以看到，访问顺序严格按照与 A 的距离（层级）进行：

第 0 层: A
第 1 层: B, C, D
第 2 层: E, F, G, H

四、BFS 的代码实现 (以 Java 为例)

4.1 图的表示：邻接表

我们首先需要一个表示图的数据结构。邻接表是实现 BFS 的常用且高效的选择。

import java.util.*;

// 定义图的结构
class Graph {
    private int V; // 顶点数量
    private LinkedList<Integer>[] adj; // 邻接表数组

    // 构造函数
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加一条边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
    
    // ... BFS 方法将在这里实现 ...
}

4.2 BFS 核心代码

（1）迭代实现

下面是在 Graph 类中实现的 BFS 方法。

// 从给定的源点 s 开始进行 BFS 遍历
void BFS(int s) {
    // 1. 初始化：创建一个布尔数组来标记访问过的顶点
    boolean[] visited = new boolean[V];

    // 2. 初始化：创建一个队列用于 BFS
    LinkedList<Integer> queue = new LinkedList<>();

    // 3. 将源点标记为已访问，并将其入队
    visited[s] = true;
    queue.add(s);

    // 4. 循环处理队列中的顶点
    while (!queue.isEmpty()) {
        // 从队列中取出一个顶点并打印
        s = queue.poll(); // poll() 方法会移除并返回队列的头部
        System.out.print(s + " ");

        // 遍历该顶点的所有邻接顶点
        for (int n : adj[s]) {
            // 如果邻接顶点尚未被访问
            if (!visited[n]) {
                // 将其标记为已访问
                visited[n] = true;
                // 将其入队
                queue.add(n);
            }
        }
    }
}

（2）处理非连通图

上述 BFS(int s) 方法只能遍历从 s 出发可达的连通分量。如果图是非连通的，我们需要一个外层循环来确保所有顶点都被访问。

// 遍历整个图（可能包含多个连通分量）
void fullGraphBFS() {
    boolean[] visited = new boolean[V]; // 共享的 visited 数组

    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            // 对每个未访问过的顶点，启动一次新的 BFS
            BFSUtil(i, visited);
        }
    }
}

// 供 fullGraphBFS 调用的辅助函数
private void BFSUtil(int s, boolean[] visited) {
    LinkedList<Integer> queue = new LinkedList<>();

    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty()) {
        s = queue.poll();
        System.out.print(s + " ");

        for (int n : adj[s]) {
            if (!visited[n]) {
                visited[n] = true;
                queue.add(n);
            }
        }
    }
}

五、BFS 的应用场景

5.1 核心应用：无权图的单源最短路径

这是 BFS 最经典、最重要的应用。

定义：在无权图（所有边的权重都为1）中，从一个源点 s 到目标点 t 的最短路径，指的是包含边数最少的路径。

（1）为什么 BFS 能找到最短路径？

因为 BFS 是逐层遍历的。它首先访问所有距离源点为 1 的顶点，然后是所有距离为 2 的顶点，以此类推。这意味着，当 BFS 第一次到达某个顶点 v 时，它所经过的路径必然是从源点 s 到 v 的最短路径之一。

如果存在一条更短的路径，那么 v 肯定会处于一个更早的层级，从而被更早地访问到，这与“第一次到达”的前提相矛盾。

（2）求解最短路径长度

我们可以稍作修改，用 BFS 计算从源点 s 到所有其他可达顶点的最短距离。

// 计算从源点 s 到所有其他顶点的最短路径长度
void shortestPathLength(int s) {
    int[] distance = new int[V]; // 存储距离
    Arrays.fill(distance, -1); // 初始化距离为 -1 (表示不可达)

    boolean[] visited = new boolean[V];
    LinkedList<Integer> queue = new LinkedList<>();

    visited[s] = true;
    queue.add(s);
    distance[s] = 0; // 源点到自身的距离为 0

    while (!queue.isEmpty()) {
        int u = queue.poll();

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                distance[v] = distance[u] + 1; // 核心：距离是父节点距离+1
                queue.add(v);
            }
        }
    }

    // 打印结果
    System.out.println("从源点 " + s + " 到各顶点的最短距离:");
    for (int i = 0; i < V; i++) {
        System.out.println("顶点 " + i + ": " + distance[i]);
    }
}

5.2 其他应用场景

寻找图中的连通分量：通过 fullGraphBFS 的方式，每次调用 BFSUtil 都能找到一个新的连通分量。
社交网络分析：寻找“六度分隔”理论中的联系，即找到两个用户之间的最短朋友链。
网络爬虫：从一个种子 URL 开始，逐层抓取网页。
检测二分图：在遍历时对节点进行染色，如果发现相邻节点颜色相同，则不是二分图。
一些特定算法的子过程：例如，在某些垃圾回收算法（如 Cheney’s algorithm）中用于遍历对象图。

六、BFS 与 DFS 的全方位对比

为了更好地理解这两种遍历算法，我们将它们进行一个全面的对比。

特性	广度优先搜索 (BFS)	深度优先搜索 (DFS)
核心思想	层层推进，地毯式搜索	一条路走到黑，不撞南墙不回头
数据结构	队列 (Queue) - 先进先出 (FIFO)	栈 (Stack) 或递归 - 后进先出 (LIFO)
搜索路径	找到的路径是最短的（对于无权图）	找到的路径不一定是最短的，但通常很深
应用场景	无权图最短路径、寻找连通分量、二分图检测	拓扑排序、寻找环、寻找连通分量、求解迷宫问题（任意解）
空间复杂度	$O (V)$ ，最坏情况需存储一层所有节点	$O (V)$ ，最坏情况（链状图）需存储整条路径
时间复杂度	$O (V + E)$ (V是顶点数, E是边数)	$O (V + E)$ (V是顶点数, E是边数)

总结一下：

想找最短路径，用 BFS。
想找是否存在路径（不要求最短），DFS 更简单（递归实现）。
想遍历所有节点，两者都可以，复杂度相同。

七、总结

今天，我们系统地学习了图的广度优先搜索（BFS），它是数据结构与算法知识体系中不可或缺的一环。通过本文的学习，我们应掌握以下核心要点：

核心思想：BFS 是一种逐层遍历的搜索算法，其行为模式类似于水波扩散，常被形容为“地毯式”搜索。
关键数据结构：BFS 依赖**队列（Queue）**的先进先出（FIFO）特性来保证其逐层访问的顺序，这与依赖栈的 DFS 形成鲜明对比。
实现细节：实现 BFS 的关键在于使用一个队列来管理待访问节点，并配合一个visited集合（或数组）来防止重复访问和无限循环。
王牌应用：BFS 最重要和最广泛的应用是解决无权图的单源最短路径问题，因为其逐层探索的性质天然保证了第一次到达某节点时所经过的路径就是最短的。
与 DFS 的区别：我们必须清晰地认识到 BFS 和 DFS 在搜索策略、辅助数据结构、应用场景上的根本差异，以便在面对具体问题时做出正确的选择。

掌握了 DFS 和 BFS 这两大图遍历利器，你就已经打开了通往更复杂图算法（如最小生成树、最短路径算法 Dijkstra 等）的大门。在接下来的文章中，我们将继续探索图论中更多有趣的算法。

乐奇 Rokid 开放社区

更多推荐

使用Rokid AIUI做了一个童年推箱子游戏

乐奇 Rokid 开放社区

基于 AIUI 框架的眼镜端坐姿监测智能体：WorkerMonitor 设计与实现

基于AIUI框架，设计并实现眼镜端坐姿监测智能体WorkerMonitor。通过加速度传感器实时采集头部姿态数据，结合校准偏移量进行三态分类（正常/警示/异常），每秒采样一次，累计时长并低打扰提醒。每2小时调用LLM生成个性化健康建议，支持自动工作/休息切换与隐藏模式，兼顾隐私与体验。项目采用Ink单文件页面结构，实现极简交互与可持续反馈，为长期伏案者提供无感式颈椎健康管理方案。

乐奇 Rokid 开放社区

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精