算法刷题系列（三十七）：图论 BFS——在无权图中求最少边数

算法刷题系列（三十七）：图论 BFS——在无权图中求最少边数

无权图中，从起点到某个顶点的最短路径，是经过边数最少的路径。广度优先搜索（BFS）从起点开始按距离一层层扩展，因此首次发现一个顶点时，得到的就是它的最少边数。

图用邻接表表示：graph[u] 列出从 u 可一步到达的邻居。无向边 {u,v} 要在两端都加入邻接表；有向边 u→v 只加入 graph[u]。

队列中的层次与多源搜索

distance[v] == -1 表示顶点尚未访问。将顶点入队时就写入距离，而不是出队后才标记；这样即使多个前驱都能到它，也只会入队一次。若有多个起点，把它们都以距离 0 入队，搜索便计算每个顶点到最近起点的最短边数。

Java 实现

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class MultiSourceBfs {
    public static int[] distances(List<List<Integer>> graph, int[] sources) {
        int n = graph.size();
        int[] distance = new int[n];
        Arrays.fill(distance, -1);
        Deque<Integer> queue = new ArrayDeque<>();

        for (int source : sources) {
            if (source < 0 || source >= n) {
                throw new IllegalArgumentException("source out of range");
            }
            if (distance[source] == -1) {
                distance[source] = 0;
                queue.addLast(source);
            }
        }

        while (!queue.isEmpty()) {
            int node = queue.removeFirst();
            for (int neighbor : graph.get(node)) {
                if (neighbor < 0 || neighbor >= n) {
                    throw new IllegalArgumentException("neighbor out of range");
                }
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[node] + 1;
                    queue.addLast(neighbor);
                }
            }
        }
        return distance;
    }
}

Python 实现

from collections import deque

def bfs_distances(
    graph: list[list[int]], sources: list[int]
) -> list[int]:
    n = len(graph)
    distance = [-1] * n
    queue: deque[int] = deque()
    for source in sources:
        if not 0 <= source < n:
            raise ValueError("source out of range")
        if distance[source] == -1:
            distance[source] = 0
            queue.append(source)

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

graph = [[1, 2], [0, 3], [0, 3], [1, 2], []]
assert bfs_distances(graph, [0, 4]) == [0, 1, 1, 2, 0]
assert bfs_distances(graph, []) == [-1, -1, -1, -1, -1]

正确性与复杂度

队列按先入先出的顺序处理顶点。所有距离为 d 的顶点先于距离为 d+1 的顶点出队；从距离 d 的顶点首次发现的邻居只需再走一条边，因此距离是 d+1。若存在更短路径，其前一层顶点会更早展开并先发现目标，与“首次发现时距离较大”矛盾。

邻接表下，每个顶点最多入队一次，每条边最多检查一次（无向边在表中出现两次），时间 O(V+E)，额外空间 O(V)。邻接矩阵实现则通常要扫描整行，时间会变为 O(V²)。

边界与易错点

• 多个源点之间重复时应去重；否则虽不影响正确性，但会重复入队。
• 没有起点时所有距离保持 -1；不可达顶点也用 -1 表示。
• 无权图才按边数用 BFS 求最短路；若边权不相等，应考虑 Dijkstra 等算法。
• 需要恢复具体路径时，发现邻居时同时记录 parent[neighbor] = node。
• 图的方向由邻接表建图方式决定；把有向图误当无向图会引入不存在的路径。

BFS 的关键不变量是首次入队即确定最短边数。多源版本只改变初始化：把每个源都放进第零层。