广度优先搜索(BFS)

目录

简介

广搜流程

例题

“叕”解救小扣

---

预计阅读时间：20分钟

简介

        广度优先搜索（Breadth First Search）又名宽度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

              图1        广度优先搜索 

        广度优先搜索适合找最优解，如图1所示：1就是从0到1；2就是从0到2；5就是从0到2到5……  

        进行广度优先搜索需要用到队列，因为广度优先搜索需要保证先访问节点的未访问临接点，恰好是先进先出。

        已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。

        之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。

        为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。

        在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根
节点，即源顶点s.在扫描已发现顶点u的临接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u 是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。

广搜流程

✓标记起始点；

✓从起始点往下搜索取所有一步可达的点，判断它们是否为目标点：

     ●如果找到目标，则结束并回传结果‘

     ●否则将它坐在的点进行标记

✓如果所有点全部被标记，表示整张图都检查过了，也就是说途中没有我们想要搜索的目标。结束搜索并回传“找不到目标”

✓重复第2步

例题

“叕”解救小扣

题目描述

有一天，小扣叕在外遇到坏人，只能先躲起来报警。警察得知后叕立即去解救无助的小扣。警察当然是有备而来，已经弄清楚了附近坏人的位置，现在警察要以最快的速度去解救小扣。问题就此叕开始了……
地图由ｎ行ｍ列的单元格组成（ｎ和ｍ都小于或等于1000），每个单元格要么是空地，要么是坏人。你的任务是帮助警察找到一条从地图起点通往小扣所在位置的最短路径。注意，遇到坏人会阻止警察解救小扣，当然警察也不能走到地图之外。

输入INPUT：

输入格式

第一行输入整数n和m，表示地图横纵方向各有多少位置能走。 接下来的n行按照数组的方式，输入地形图。有坏人的地方输入1，其他输入0。 第n+2行输入4个整数，分别表示警察的横纵坐标和小扣的横纵坐标。

输入样例

5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3

输出OUTPUT：

输出格式

解救小扣的最短路径值，如果不可能救到小扣输出-1。

输出样例

7

题目分析：

        如果不需要求最短路径的话，深度优先搜索是绝对可以的，但是现在要求的是解救小扣的最短路径，所以深度优先搜索肯定用不了了，只能用广度优先搜索了。

解题思路：

        定义数组a来存储地图

int a[1005][1005];

        广度优先搜索的方法：通过“一层一层”扩展的方法来找到小扣。扩展是没发现一个点就将这个点加入到队列中，直至走到小扣的位置（dr,dc）时为止。

        警察在入口(1,1)处，一步之内可以到达的点有(1,2)和(2,1)。

        但是小扣并不在这两个点上，那警察只能通过(1,2)和(2,1)这两个点继续走下去。

        现在警察走到了(1,2)这个点，之后他又能够走到哪些新的点呢？有(2,2)。

        再看看通过(2,1)又可以达到那些点呢？可以达到(2,2)和(3,1)。

        此时你会发现(2,2)这个点即可以从(1,2)到达，也可以从(2,1)到达，并且都只用了2步。为了防止一个点多次被走到，需要判断当前点是否已经存储距离了。

        可以定义数组dis来存储当前位置是否来过。

int dis[1005][1005]={0x3f3f3f};

        此时警察2步可以走到的点都全部走到了，有(2,1)和(3,1)，可是小扣并不在这两个点上。

        没有别的办法，还得继续往下尝试，看看通过(2,2)和(3,1)这两个点还能到达哪些新的哪有走到过的点。

        通过(2,2)这个点可以到达(2,3)和(3,2)，通过(3,1)可以到达(3,2)和(4,1)。

        现在3步可以到达的点有（2,3）、（3,2）和（4,1）。依旧没有到达小扣的所在点，我们需要重复刚才的方法，直到到达小扣所在的点为止。

参考代码

#include 
#include 
#include 
using namespace std;
int n,m,a[1001][1001],dis[1001][1001],sx,sy,ex,ey;
const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
void bfs()
{
	queue <int> qx,qy;
	qx.push(sx),qy.push(sy);
	dis[sx][sy]=0;
	while(!qx.empty())
	{
		int x=qx.front(),y=qy.front();
		qx.pop();
		qy.pop();
		for(int i=0; i<4; i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==0&&dis[nx][ny]==0x3f3f3f3f)
			{
				dis[nx][ny]=dis[x][y]+1;
				if(nx==ex&&ny==ey)
				{
					return;
				}
				qx.push(nx),qy.push(ny);
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	memset(dis,0x3f,sizeof(dis));
	bfs();
	if(dis[ex][ey]==0x3f3f3f3f)
	{
		cout<<-1<
	}
	else
	{
		cout<
	}
	return 0;
}

感谢阅读！