BFS 求无权图最短路径

为什么需要BFS 求无权图最短路径

在无权图（或边权均为 1 的图）中，"最短路径"就是经过最少边数的路径。BFS 天然按层次展开搜索，第一次到达某个顶点时所经过的边数就是最短距离，因此 BFS 是求解无权图单源最短路径的最优方法。

408 考研中，BFS 求最短路径是图的遍历章节的重要延伸，常以算法设计题或选择题的形式出现，需要掌握距离数组 d[] 和路径记录数组 path[] 的使用。

核心思想

BFS 求无权图最短路径的核心特点：

逐层扩展：BFS 按照距离源点由近到远的顺序访问顶点，第 k 层的顶点距离源点恰好为 k
首次到达即最短：由于逐层扩展的特性，某顶点第一次被访问时的距离一定是最短距离
距离数组 d[]：d[v] 记录源点到顶点 v 的最短距离，初始化为 -1（表示未访问）
路径数组 path[]：path[v] 记录顶点 v 的前驱顶点，用于回溯还原最短路径

搜索过程示意：

层次 0:  源点 s         → d[s] = 0
层次 1:  s 的邻接顶点    → d[v] = 1
层次 2:  层次1的邻接顶点  → d[v] = 2
  ...

交互可视化

通过下方的交互动画，你可以逐步观察BFS 求无权图最短路径的执行过程：

加载可视化中...

操作详解

算法思路

关键步骤：

初始化距离数组 d[] 全部为 -1，路径数组 path[] 全部为 -1
将源点 s 入队，设 d[s] = 0
当队列非空时，取出队头顶点 u，遍历 u 的所有邻接顶点 v：
- 若 d[v] == -1（未访问），则 d[v] = d[u] + 1，path[v] = u，将 v 入队
遍历结束后，d[] 中即为源点到各顶点的最短距离

// BFS 求无权图单源最短路径
// 邻接表存储，n 个顶点（编号 0 ~ n-1），源点为 s
void BFS_ShortestPath(int s, int n) {
    int d[MAX_V], path[MAX_V];
    bool visited[MAX_V];
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) {
        d[i] = -1;      // -1 表示不可达
        path[i] = -1;   // -1 表示无前驱
    }

    Queue Q;
    InitQueue(&Q);
    d[s] = 0;
    visited[s] = true;
    EnQueue(&Q, s);

    while (!IsEmpty(&Q)) {
        int u;
        DeQueue(&Q, &u);
        // 遍历 u 的所有邻接顶点 v
        for (int v = FirstNeighbor(u); v >= 0; v = NextNeighbor(u, v)) {
            if (!visited[v]) {
                d[v] = d[u] + 1;   // 距离 = 前驱距离 + 1
                path[v] = u;        // 记录前驱
                visited[v] = true;
                EnQueue(&Q, v);
            }
        }
    }
}

路径还原：从目标顶点 t 沿 path[] 回溯到源点 s，逆序即为最短路径。

// 输出从 s 到 t 的最短路径（逆序回溯后正序打印）
void PrintPath(int s, int t, int path[]) {
    if (t == -1 || d[t] == -1) return;  // 不可达
    int stack[MAX_V], top = -1;
    for (int v = t; v != -1; v = path[v])
        stack[++top] = v;
    while (top >= 0)
        printf("%d ", stack[top--]);
}

执行过程详解

以下图为例，求从顶点 0 出发到所有顶点的最短路径：

    0 --- 1 --- 3
    |     |
    2 --- 4 --- 5

步骤	队列状态	当前顶点 u	发现的邻接顶点	d[] 更新	path[] 更新
初始		-	-	d[0]=0	-
1		0	1, 2	d[1]=1, d[2]=1	path[1]=0, path[2]=0
2		1	3, 4	d[3]=2, d[4]=2	path[3]=1, path[4]=1
3		2	4(已访问)	-	-
4		3	-	-	-
5		4	5	d[5]=3	path[5]=4
6	{}	5	-	-	-

为什么 BFS 能保证最短？ 因为 BFS 使用队列（FIFO），先发现的顶点先处理，同一层的顶点一定在下一层之前全部处理完毕。因此当顶点 v 第一次被发现时，当前的层数就是 s 到 v 的最短距离——不可能存在更短的路径，否则 v 应该在更早的层次被发现。

BFS vs Dijkstra：

对比项	BFS	Dijkstra
适用图	无权图（边权均为 1）	带权图（非负权）
时间复杂度	O(V + E)	O((V+E) log V)（优先队列）
数据结构	普通队列	优先队列（最小堆）
核心原理	逐层扩展，层数即距离	贪心选择当前最短距离顶点
考研考查	算法设计题、选择题	求最短路径值、手动模拟

复杂度分析

指标	复杂度	说明
时间复杂度（邻接表）	O(V + E)	每个顶点入队一次，每条边检查一次
时间复杂度（邻接矩阵）	O(V²)	每个顶点需扫描一整行寻找邻接顶点
空间复杂度	O(V)	队列 + visited[] + d[] + path[] 均为 O(V)

空间复杂度：O(V)，需要队列、访问标记数组、距离数组和路径数组各占 O(V) 空间。

考研高频考点

⭐ BFS 为什么能求无权图最短路径（逐层扩展，首次到达即最短——简答题/选择题高频）
⭐ d[] 和 path[] 数组的作用与初始化方式（算法设计题必考）
⭐ BFS 与 Dijkstra 的适用场景区分（选择题高频：无权图用 BFS，带权图用 Dijkstra）
⭐ 给定图手动模拟 BFS 求最短路径过程（填空题/选择题）
邻接表 vs 邻接矩阵对 BFS 时间复杂度的影响（O(V+E) vs O(V²)）
路径还原的回溯方法（利用 path[] 逆序追踪）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

BFS 求无权图最短路径 ​

为什么需要BFS 求无权图最短路径 ​

核心思想 ​

交互可视化 ​

操作详解 ​

算法思路 ​

执行过程详解 ​

复杂度分析 ​

考研高频考点 ​

相关文章