算法竞赛学习周记——广度优先搜索（BFS）

什么是广搜

广搜，即广度优先搜索，是一种基于队列这种数据结构的搜索算法。

队列

即先进先出表队列主要涉及两种操作，出队和入队。在模拟这两种操作时，要设两个指针head和tail，指代队首和队尾。

head:指向队首的前一个元素

tail:指向队尾元素

当head=2，tail=4时，队列中共有4-2=2个元素。同理，每时每刻队列中共有tail-head个元素（以下head简称h，tail简称t）

出队：++h;//后移一位，相当于队首后移一位

入队：++t；que[t]=val;//val值入队，队尾向后移一个位置。

实质

广搜即通过队列反复入队出队的过程。

广搜模板

void bfs(所传参数)
{
	队列初始化，起点入队
	while(h<t)//判断队列是否非空
	{
		++h//出队
		for(   )//节点扩展规则
			if(能扩展出节点&&该点未被其他节点扩展时访问)
			{
				++t;//元素准备入队
				入队，在队列中保存结果
				if（该点为目标节点）
				{
					处理结果
					h=t;//准备退出
					break;
				}
			}
	}
}
           

广搜路径打印

广搜是通过记录前驱结点，最后顺藤摸瓜实现打印路径的。设pre[] 数组，用来记录前驱结点。当扩展出

一个结点时，记录：pre[t]=h 。是队列中的编号。

广搜连通块问题

同DFS的搜索机制相似，扩展节点并标记，双层for循环遍历二维数组，同时记录调用函数的次数。

广搜与深搜的比较

1.dfs基于递归，bfs基于队列。

2.dfs是“一条路走到底”，bfs是“地毯式搜索”。

3.dfs的时间复杂度很高，往往需要剪枝。bfs首次搜到的是最优解，但是对空

间的要求高（主要是队列需要空间）。

4.dfs 适用于求出所有解，bfs 适用于求出最优解。有时还需要对dfs求出的所有

解进行比较，确定一个最优解，但利用dfs求最优解，时间复杂度高。

5.dfs和bfs都是非常优秀的搜索算法，更要多加练习。