BFS适用

字数

680 字

阅读时间

3 分钟

---

BFS的性质/用途

• BFS性质：
  1. 宽搜（BFS）第一次搜索就能搜索到最小值，所以如果是要求“最小”，则选用BFS
  2. BFS是基于迭代的搜索算法，不会爆栈
• BFS好处：当所有边的权重都相等时，用宽搜从起点开始搜，可以得到所有点的单源最短路（所有点到起点的最短路）
• 一般用数组模拟队列
• BFS具有两段性，即：在队列元素 $[hh,tt]$ 中，只有距离为 $x$ 和 $x+1$ 的点，因为bfs会先将距离每个队头元素的最近的点加入队尾，再往后移动，所以在距离为 $x$ 的点遍历完全之前，队列 $[hh,tt]$ 中仍然只会有 $x$ 和 $x+1$ 这两段距离
• BFS具有单调性，即：队列中的元素（距离）都是单调递增的

数组模拟队列的注意事项

• 全局变量：
  推荐用于大数组（如本题的M = 1e6）。
  避免栈溢出，且通过合理设计（如每次调用重置指针）可安全复用内存。

• 局部变量：
  仅适用于小规模数组（如M ≤ 1e4）。
  需确保数组大小在栈容量内，适合简单场景或递归深度可控的情况。

若M = 1e6较大，必须将q设为全局变量或动态分配，否则局部变量会导致栈溢出。若数组较小（如M ≤ 1e4），局部变量更安全且封装性更好。实际开发中，优先使用std::vector兼顾灵活性和安全性。

有关bfs函数中变量tt的初始化

若是自己在bfs函数中定义模拟队列数组的第一个元素（适用于单源最短路），则可以初始化tt为0，如：

写法一：
void bfs(int sx, int sy)
{
	int hh = 0, tt = 0;
	q[0] = {sx, sy};
}

写法二：
void bfs(int sx, int sy)
{
	int hh = 0, tt = -1;
	q[++ tt] = {sx, sy};
}

一般采用第一种写法

若是多源最短路模型，则需要将所有起点均加入到模拟队列数组中，故只能定义tt为-1

void bfs(int sx, int sy)
{
	int hh = 0, tt = -1;
	for (int i = 0; i < n; i ++) // 一共是 n × n 的迷宫/网格
		for (int j = 0; j < n; j ++)
			if (g[i][j] == '#') // 如果该点是起点，则加入队列的队头
				q[++ tt] = {i, j};
}

贡献者

freeway348

文件历史

最后编辑于 12 天前查看完整历史

4ab72-ma1