背景：太好了，D老师终于于2025年5月10日正式讲完了搜索算法的最后一课——BFS综合，做此blog表达我的喜悦。

---

广度优先搜索（BFS/冰法师）

上次的搜索算法1有点粗略了，这次将细一点

深度优先搜索，即Depth-First Search，简称DFS。又因为它用途大，所以我们戏称它为大法师。

以此类推。广度优先搜索，即Breadth-First Search，简称BFS。又因为它善于求最短路，所以我们戏称它为冰法师。

如果用图来表示DFS和BFS的搜索路径，如下图所示（图片由D老师提供）：

可以发现：绿色的路径是DFS，它绕来绕去，还要回溯，所以搜到第9个点才搜到粉小拨鼠。而同样的图，黄色的路径是BFS，它不需要回溯，只需要第3次就能搜到粉小拨鼠。由此可以看出，BFS的效率要比DFS高很多。

回顾上节搜索算法，可以推出DFS的模版：

void dfs(参数列表)
{
	if (到达终点)
	{
		记录;
		返回; 
	}
	(记忆化剪枝;)
	for (所有拓展状态)
	{
		if(新状态可行)
		{
			记录;
			dfs(新状态);
			(回溯);
		}
	}
}

那BFS有没有模版呢？答案是肯定的。那怎么实现呢？

仿照上面的图，先在一个容器中加入最上面的点，把与它相连的点加入，在把最上面的点删掉，以此类推。可以很容易的发现，符合这种先进先出的容器正是队列（其实D老师的图片下方已经写出用队列了）。BFS的搜索怎么用代码实现呢？还是上面的图，只要没有遍历完（队列不为空），就循环，先拿出第一个要检查的节点（取出队首元素），出队，检查它是不是目标点，是就结束(return)，否则就遍历它的所有推展的节点，入队，如此循环。直到最外层循环结束（队列为空），就说明没有找到目标点，输出类似-1或No。由此可以推出BFS的模板：

queue <类型> 队列名;
队列名.push(初始状态);
while (队列不为空)
{
	类型 f = 队列名.front();
	队列名.pop();
	if (到达终点)
	{
		返回 
	}
	for (所有拓展状态)
	{
		if (新状态可行)
		{
			记录;
			新状态入队; 
		}
	}
}
return 不可行;

（DFS和BFS模板）

了解了这些之后，看看D老师的训练吧。

目录：

1. 广搜基础-广搜实现深搜
2. 最小步数、最短路径问题
3. 综合BFS
4. 进阶BFS：搜索和剪枝

---

1.广搜基础-广搜实现深搜

这个好像没什么好说。运用深搜的思维就好了。

---

D老师在今天（2025/5/24）开始讲二分查找了，终于想起要写这篇blog。。。

---

2.最小步数、最短路径问题

广搜天然适合搜索最短路径。应为只要一搜到，那路径一定是最短的，直接返回答案。又加上广搜运用的方式，使得它做多把所有节点遍历一遍，因此广搜的时间复杂度为$O(n)$。

---

3.综合BFS

综合，就是综合嘛

---

4.进阶BFS：搜索和剪枝

这个。。。D老师好像没则么讲，只给了两个提示：

1. 尽量少入队
2. 运用优先队列

1.尽量少入队

类似于DFS，如果达到什么条件才入队。

---

若想要熟练得掌握BFS，还需努力刷题：内阁会议、八数码难题

不要说这篇blog比上次短，因为D老师也就讲了两节课。