BFS：按距离分层扩展状态｜算法讲义

解决什么问题#

广度优先搜索（BFS）从起点开始，先访问距离为 1 的状态，再访问距离为 2 的状态，依次向外扩张。它适合：

求无权图中的最少边数和一条最短路径；
在网格中求每步代价相同的最少移动次数；
按层遍历树或隐式状态图；
判断可达性、二分图染色或计算连通范围。

这里的“无权”也包括所有边权相同的情况。若边权不同，普通 FIFO 队列不再保证最短距离顺序。

核心思想与不变量#

BFS 使用先进先出队列。起点距离为 0；从距离为 $d$ 的节点第一次发现邻居时，将邻居距离设为 $d+1$ 并入队。

算法维持以下分层不变量：

队列中节点的距离单调不减；一个节点第一次入队时，已经找到从起点到它的最短路径。

证明可按距离归纳。距离小于 $d$ 的节点会先于距离为 $d$ 的节点出队，因此如果某节点第一次由第 $d$ 层发现，任何更短路径都应当更早发现它，与“第一次”矛盾。

parent[v] 记录第一次发现 v 的前驱。沿前驱反向走回起点，再翻转序列，就得到一条最短路径。

复杂度#

使用邻接表时，每个顶点最多入队一次，每条边最多被检查两次（无向图）或一次（有向图），所以时间复杂度为 $O(V+E)$ ，距离、前驱和队列共占 $O(V)$ 空间。

若使用邻接矩阵，每次出队都需要扫描整行，时间会变成 $O(V^2)$ 。

C++17 模板：无权图最短路与路径恢复#

顶点编号为 0..n-1。不可达顶点的距离和前驱均为 -1。

#include <algorithm>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <vector>

struct BFSResult {
  std::vector<int> distance;
  std::vector<int> parent;
};

BFSResult bfs(const std::vector<std::vector<int>>& graph, int source) {
  const int n = static_cast<int>(graph.size());
  if (source < 0 || source >= n) {
    throw std::out_of_range("source is outside the graph");
  }

  BFSResult result{std::vector<int>(n, -1), std::vector<int>(n, -1)};
  std::queue<int> pending;

  result.distance[source] = 0;
  pending.push(source);

  while (!pending.empty()) {
    const int vertex = pending.front();
    pending.pop();

    for (int next : graph[vertex]) {
      if (next < 0 || next >= n) {
        throw std::out_of_range("an edge endpoint is outside the graph");
      }
      if (result.distance[next] != -1) {
        continue;
      }
      // 在入队时标记，确保每个顶点只入队一次。
      result.distance[next] = result.distance[vertex] + 1;
      result.parent[next] = vertex;
      pending.push(next);
    }
  }
  return result;
}

std::vector<int> restore_path(int source, int target,
                              const std::vector<int>& parent) {
  if (source < 0 || target < 0 ||
      source >= static_cast<int>(parent.size()) ||
      target >= static_cast<int>(parent.size())) {
    throw std::out_of_range("path endpoint is outside the graph");
  }

  std::vector<int> path;
  for (int vertex = target; vertex != -1; vertex = parent[vertex]) {
    path.push_back(vertex);
  }
  if (path.back() != source) {
    return {};  // target 不可达
  }
  std::reverse(path.begin(), path.end());
  return path;
}

int main() {
  std::vector<std::vector<int>> graph(5);
  const auto add_edge = [&](int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
  };
  add_edge(0, 1);
  add_edge(0, 2);
  add_edge(1, 3);
  add_edge(2, 3);
  add_edge(3, 4);

  const BFSResult result = bfs(graph, 0);
  const std::vector<int> path = restore_path(0, 4, result.parent);

  std::cout << "distance = " << result.distance[4] << "\npath:";
  for (int vertex : path) {
    std::cout << ' ' << vertex;
  }
  std::cout << '\n';
}

C++17 模板：双向 BFS#

当图无权、起点和终点明确，并且能从终点构造反向搜索时，可以从两端轮流扩展完整的一层。若最短路长度为 $d$ 、平均分支数为 $b$ ，单向 BFS 可能扩展到约 $b^d$ 个状态，而两端相遇通常只需各自走到深度约 $d/2$ 。

下面模板用于无向图。两侧分别保存距离；新发现节点若已经被另一侧访问，两个距离之和就是一条连接路径。为了不让邻接表顺序影响答案，expand_one_layer 会完成当前整层，并取这一层所有相遇候选的最小值。

#include <algorithm>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <vector>

int expand_one_layer(const std::vector<std::vector<int>>& graph,
                     std::queue<int>& frontier, std::vector<int>& own_distance,
                     const std::vector<int>& other_distance) {
  const int n = static_cast<int>(graph.size());
  const int layer_size = static_cast<int>(frontier.size());
  int best_meeting_distance = -1;

  for (int count = 0; count < layer_size; ++count) {
    const int vertex = frontier.front();
    frontier.pop();

    for (int next : graph[vertex]) {
      if (next < 0 || next >= n) {
        throw std::out_of_range("an edge endpoint is outside the graph");
      }
      if (own_distance[next] != -1) {
        continue;
      }

      own_distance[next] = own_distance[vertex] + 1;
      frontier.push(next);
      if (other_distance[next] != -1) {
        const int candidate = own_distance[next] + other_distance[next];
        if (best_meeting_distance == -1) {
          best_meeting_distance = candidate;
        } else {
          best_meeting_distance = std::min(best_meeting_distance, candidate);
        }
      }
    }
  }
  return best_meeting_distance;
}

int bidirectional_bfs(const std::vector<std::vector<int>>& graph,
                      int source, int target) {
  const int n = static_cast<int>(graph.size());
  if (source < 0 || source >= n || target < 0 || target >= n) {
    throw std::out_of_range("endpoint is outside the graph");
  }
  if (source == target) {
    return 0;
  }

  std::vector<int> from_source(n, -1);
  std::vector<int> from_target(n, -1);
  std::queue<int> source_frontier;
  std::queue<int> target_frontier;
  from_source[source] = 0;
  from_target[target] = 0;
  source_frontier.push(source);
  target_frontier.push(target);

  while (!source_frontier.empty() && !target_frontier.empty()) {
    int answer = expand_one_layer(graph, source_frontier, from_source,
                                  from_target);
    if (answer != -1) {
      return answer;
    }

    answer = expand_one_layer(graph, target_frontier, from_target,
                              from_source);
    if (answer != -1) {
      return answer;
    }
  }
  return -1;
}

int main() {
  std::vector<std::vector<int>> graph(6);
  const auto add_edge = [&](int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
  };
  add_edge(0, 1);
  add_edge(1, 2);
  add_edge(2, 3);
  add_edge(3, 4);
  add_edge(4, 5);
  add_edge(1, 4);

  std::cout << "distance = " << bidirectional_bfs(graph, 0, 5) << '\n';
}

若原图是有向图，终点一侧必须沿反向边搜索，不能直接复用原邻接表。实际实现也常选择扩展当前节点数较少的一侧；此时仍需按层扩展，并谨慎维护停止条件。

示例推演#

示例图从 0 出发：

第 0 层：0
第 1 层：1, 2
第 2 层：3
第 3 层：4

顶点 3 可能同时与 1、2 相邻，但第一次由 1 发现时就立刻标记，因此不会重复入队。恢复出的路径可以是 0 → 1 → 3 → 4，长度为 3。

易错点#

在出队时才标记访问，导致同一顶点被多个前驱重复加入队列。
把“第一次到达最短”用于带不同权值的边。普通 BFS 只适用于等权移动。
多组数据之间没有重置距离、前驱或队列。
网格 BFS 忘记先检查边界，再访问数组。
只记录距离却在最后要求输出路径；需要在首次发现时同步保存前驱。
遍历非连通图时只从一个起点运行 BFS，因而漏掉其他连通分量。