算法刷题系列（三十）：BFS——按层扩展状态空间

算法刷题系列（三十）：BFS——按层扩展状态空间

广度优先搜索（BFS）使用队列，先处理距离起点一步的状态，再处理距离两步的状态。对边权都相同的图，这种层次顺序使一个节点第一次被发现时，得到的就是从起点到它的最少边数。

这和上一篇 DFS 的适用目标不同：DFS 可以找到一条可达路径，但不保证路径最短；BFS 为最短路付出维护队列与距离数组的代价。若边权不同，普通 BFS 不再保证最短加权距离，应考虑 0-1 BFS、Dijkstra 等算法。

一、层次与最短路证明

把起点距离设为 0，放入队列。出队节点 u 时，尝试访问尚未发现的邻居 v，设置 dist[v] = dist[u] + 1 并入队。

若存在一条更短路径到 v，它最后一条边必从某个更浅层节点进入；BFS 会先处理那些更浅层节点，因此应当更早发现 v，与“此时才首次发现”矛盾。故首次赋值即最短边数。发现时立刻标记，而不是出队后才标记，可避免同层多个节点重复入队。

二、Java：距离与路径恢复

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class Main {
    static final class SearchResult {
        final int[] distance;
        final int[] parent;
        SearchResult(int[] distance, int[] parent) {
            this.distance = distance;
            this.parent = parent;
        }
    }

    static SearchResult bfs(List<List<Integer>> graph, int start) {
        int n = graph.size();
        if (start < 0 || start >= n) {
            throw new IllegalArgumentException("start vertex is out of range");
        }
        int[] distance = new int[n];
        int[] parent = new int[n];
        Arrays.fill(distance, -1);
        Arrays.fill(parent, -1);
        Queue<Integer> queue = new ArrayDeque<>();
        distance[start] = 0;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            for (int neighbor : graph.get(vertex)) {
                if (neighbor < 0 || neighbor >= n) {
                    throw new IllegalArgumentException("neighbor is out of range");
                }
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[vertex] + 1;
                    parent[neighbor] = vertex;
                    queue.offer(neighbor);
                }
            }
        }
        return new SearchResult(distance, parent);
    }

    static List<Integer> pathTo(SearchResult result, int target) {
        if (target < 0 || target >= result.distance.length
                || result.distance[target] == -1) {
            return List.of();
        }
        List<Integer> path = new ArrayList<>();
        for (int node = target; node != -1; node = result.parent[node]) {
            path.add(node);
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(List.of(1, 2));
        graph.add(List.of(0, 3));
        graph.add(List.of(0, 3, 4));
        graph.add(List.of(1, 2, 5));
        graph.add(List.of(2));
        graph.add(List.of(3));
        SearchResult result = bfs(graph, 0);
        assert result.distance[5] == 3;
        assert pathTo(result, 5).equals(List.of(0, 1, 3, 5))
                || pathTo(result, 5).equals(List.of(0, 2, 3, 5));
        assert result.distance[0] == 0;
        assert pathTo(result, 99).isEmpty();
    }
}

三、Python：无权图最短距离

from collections import deque

def bfs_distances(graph: list[list[int]], start: int) -> tuple[list[int], list[int]]:
    if not 0 <= start < len(graph):
        raise ValueError("start vertex is out of range")
    distance = [-1] * len(graph)
    parent = [-1] * len(graph)
    distance[start] = 0
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if not 0 <= neighbor < len(graph):
                raise ValueError("neighbor vertex is out of range")
            if distance[neighbor] == -1:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return distance, parent

def restore_path(parent: list[int], distance: list[int], target: int) -> list[int]:
    if not 0 <= target < len(distance) or distance[target] == -1:
        return []
    path: list[int] = []
    node = target
    while node != -1:
        path.append(node)
        node = parent[node]
    return path[::-1]

graph = [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2], [3]]
distance, parent = bfs_distances(graph, 0)
assert distance[5] == 3
assert restore_path(parent, distance, 5) in ([0, 1, 3, 5], [0, 2, 3, 5])
assert restore_path(parent, distance, 4) == [0, 2, 4]
assert restore_path(parent, distance, 99) == []

四、复杂度、边界与常见错误

邻接表下每个顶点最多入队一次、每条边最多检查一次，时间为 O(V + E)，距离、父节点、队列最多占 O(V) 空间。无向图通常在邻接表中以两个方向存储每条边；有向图则按有向边数计算。

• -1 表示不可达，与起点距离 0 区分；不要把默认的 0 误当成未访问标记。
• 起点的父节点保持 -1；路径恢复从终点沿父指针回到起点，再反转。
• 多条等长最短路径时，返回哪一条取决于邻居遍历顺序，但距离都正确。
• 必须在入队时标记已发现；若等到出队，环和汇合路径可能导致重复入队。
• 对带不同权重的边，层数不是总权重，不能直接使用此算法宣称最短加权路径。

小结与衔接

BFS 用队列把状态空间按距离分层；在无权图或等权边图中，首次访问即得到最少边数。DFS 更适合深入探索与路径约束，BFS 则适合最短步数及层次问题。后续遇到状态图时，先明确状态、转移和边权，再决定搜索顺序。