数据结构与算法 / 系统课时

广度优先搜索

广度优先搜索

广度优先搜索按照“离起点的边数从少到多”扩展顶点。本课使用队列完成遍历,并在第一次发现顶点时记录距离与前驱,从而在无权图中恢复一条最短路径。

学习目标

  • 理解队列为何能保证按层访问顶点。
  • 使用 visited、distance 和 parent 记录遍历状态。
  • 在无权图中计算最短距离并恢复具体路径。

知识导图

text
广度优先搜索
├── 初始化
│   ├── 起点入队
│   ├── 标记已访问
│   └── 距离设为 0
├── 分层扩展
│   ├── 队首出队
│   ├── 扫描邻接点
│   └── 未访问顶点入队
└── 最短路径
    ├── distance 记录边数
    ├── parent 记录前驱
    └── 从终点反向恢复路径

问题背景或应用场景

社交关系中的“最少经过几个人”、网格地图中的“最少移动次数”、依赖网络中的“最少跳数”,都可以抽象为无权图最短路径。这里的“无权”表示每条边的代价相同,因此只需比较经过的边数。

BFS 也是后续学习拓扑层次、二分图判定和多源最短路的基础。它与深度优先搜索的主要差异不在于是否访问所有顶点,而在于待处理顶点的组织方式:BFS 使用先进先出的队列。

核心原理

队列中始终保存已经发现、但邻接边尚未全部扫描的顶点。起点距离为 0;当距离为 dd 的顶点出队时,新发现的邻接点距离一定为 d+1d+1。由于队列先进先出,距离更小的顶点总会先被处理。

广度优先搜索分层扩展与前驱树

对于邻接表表示的图,每个顶点最多入队一次,每条边最多被扫描一次,因此时间复杂度为 O(V+E)O(V+E),额外空间复杂度为 O(V)O(V)。若使用邻接矩阵,扫描每个顶点的整行,时间复杂度会变为 O(V2)O(V^2)。

首次发现某个顶点时必须立即标记已访问,而不是等它出队后再标记。这样可以防止同一顶点被多个前驱重复加入队列。

基础用法

一次标准 BFS 可以按以下顺序执行:

  1. 将所有距离初始化为 -1,表示尚不可达。
  2. 将起点加入 ArrayDeque,同时设置 distance[start] = 0。
  3. 每次取出队首顶点,依次扫描其邻接点。
  4. 对尚未访问的邻接点设置距离和前驱,并立即入队。
  5. 需要路径时,从终点沿 parent 反向回溯,再将结果反转。

distance[target] == -1 表示终点与起点不连通。起点到自身的最短距离为 0,恢复出的路径只包含起点。

完整可运行示例

下面的 Java 17 程序构造一个无向图,从顶点 A 开始遍历,并输出到 F 的最短路径。将代码保存为 BFSShortestPathDemo.java。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

public class BFSShortestPathDemo {

    private static final String[] LABELS = {"A", "B", "C", "D", "E", "F"};

    private static final class Result {
        private final List<Integer> order;
        private final int[] distance;
        private final int[] parent;

        private Result(List<Integer> order, int[] distance, int[] parent) {
            this.order = order;
            this.distance = distance;
            this.parent = parent;
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = createGraph(LABELS.length);
        addUndirectedEdge(graph, 0, 1);
        addUndirectedEdge(graph, 0, 2);
        addUndirectedEdge(graph, 1, 3);
        addUndirectedEdge(graph, 2, 3);
        addUndirectedEdge(graph, 2, 4);
        addUndirectedEdge(graph, 3, 5);
        addUndirectedEdge(graph, 4, 5);

        Result result = bfs(graph, 0);

        System.out.println("BFS order: " + formatVertices(result.order));
        System.out.println("Distances from A:");
        for (int vertex = 0; vertex < LABELS.length; vertex++) {
            System.out.println(LABELS[vertex] + " = " + result.distance[vertex]);
        }

        List<Integer> path = buildPath(result.parent, result.distance, 0, 5);
        System.out.println("Shortest path A -> F: " + formatPath(path));
    }

    private static Result bfs(List<List<Integer>> graph, int start) {
        int vertexCount = graph.size();
        int[] distance = new int[vertexCount];
        int[] parent = new int[vertexCount];
        java.util.Arrays.fill(distance, -1);
        java.util.Arrays.fill(parent, -1);

        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        // 入队时立即标记,保证每个顶点最多进入队列一次。
        distance[start] = 0;
        queue.addLast(start);

        while (!queue.isEmpty()) {
            int current = queue.removeFirst();
            order.add(current);

            for (int next : graph.get(current)) {
                if (distance[next] != -1) {
                    continue;
                }
                distance[next] = distance[current] + 1;
                parent[next] = current;
                queue.addLast(next);
            }
        }

        return new Result(order, distance, parent);
    }

    private static List<Integer> buildPath(
            int[] parent, int[] distance, int start, int target) {
        if (distance[target] == -1) {
            return Collections.emptyList();
        }

        List<Integer> reversed = new ArrayList<>();
        for (int current = target; current != -1; current = parent[current]) {
            reversed.add(current);
            if (current == start) {
                break;
            }
        }
        Collections.reverse(reversed);
        return reversed;
    }

    private static List<List<Integer>> createGraph(int vertexCount) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertexCount; i++) {
            graph.add(new ArrayList<>());
        }
        return graph;
    }

    private static void addUndirectedEdge(
            List<List<Integer>> graph, int first, int second) {
        graph.get(first).add(second);
        graph.get(second).add(first);
    }

    private static String formatVertices(List<Integer> vertices) {
        List<String> labels = new ArrayList<>();
        for (int vertex : vertices) {
            labels.add(LABELS[vertex]);
        }
        return String.join(" ", labels);
    }

    private static String formatPath(List<Integer> path) {
        if (path.isEmpty()) {
            return "unreachable";
        }
        List<String> labels = new ArrayList<>();
        for (int vertex : path) {
            labels.add(LABELS[vertex]);
        }
        return String.join(" -> ", labels);
    }
}

编译并运行:

bash
javac BFSShortestPathDemo.java
java BFSShortestPathDemo

预期输出

text
BFS order: A B C D E F
Distances from A:
A = 0
B = 1
C = 1
D = 2
E = 2
F = 3
Shortest path A -> F: A -> B -> D -> F

邻接点的存储顺序可能改变遍历顺序以及被选中的具体最短路径,但不会改变最短距离。示例中 B 先于 C 被扫描,因此 D 的前驱被记录为 B。

Tips

  • Java 中优先使用 ArrayDeque 实现队列,避免 LinkedList 的额外节点开销。
  • 多次从不同起点执行 BFS 时,可以复用图结构,但每次都要重新初始化距离和前驱数组。
  • 只需要最短距离时可以不保存 parent;只需要判断是否可达时,可以在发现目标后提前结束。
  • 多个起点同时入队且距离都设为 0,可以得到“到最近起点的距离”。

常见错误

1. 出队后才标记访问

错误表现是同一顶点被重复入队,队列膨胀,前驱也可能被反复覆盖。正确做法是在设置距离和前驱的同一时刻完成访问标记。

2. 将 BFS 用于一般加权图

BFS 只保证边权相同情况下的最短路径。若边权为非负但不全相同,应使用 Dijkstra 算法;若边权只包含 0 和 1,可使用 0-1 BFS。

3. 忘记处理不可达终点

直接沿 parent 回溯可能得到错误路径或陷入无效访问。恢复路径前应先检查 distance[target] 是否为 -1。

本课练习

  1. 在示例图中新增顶点 G,并连接 C-G、G-F。要求输出从 A 到所有顶点的距离,验收条件是 G 的距离为 2。
  2. 修改程序,使其接收任意起点和终点;当终点不可达时输出 unreachable,且不得抛出异常。
  3. 实现多源 BFS:同时以 A 和 F 为起点,计算每个顶点到最近起点的距离,并验证 D 的距离为 1。

本课总结

  • BFS 依靠先进先出的队列按距离层次扩展顶点。
  • 在首次发现顶点时记录 distance 与 parent,即可得到无权图最短距离和具体路径。
  • 邻接表实现的 BFS 时间复杂度为 O(V+E)O(V+E),并能通过 -1 距离识别不可达顶点。

下一课预告

下一课将学习“深度优先搜索”,比较递归与显式栈两种实现,并用发现、完成状态刻画搜索过程。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

广度优先搜索

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通