[数据结构与算法]算法浅谈bfs

昨天说了dfs，今天当然要聊聊我们的bfs啦，在一定情况下我们的bfs是要比dfs优越点的，特别是在寻找最短路径的时候，我bfs输出的就是最短的。dfs还要比较。。。

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

当然我们不可能聊到树，因为我还没学QAQ。
并且，会在以后讲图的遍历中的bfs。
我认为的bfs就是队列加迭代

2. 队列简介

在介绍bfs之前，当然要先说说他的好基友，队列啊！
队列，队列，顾名思义排了队的序列。
我们接着用一道题来说一说队列。
题目：肖恩问佩琪要QQ，但是佩琪没有直接给肖恩，而是给了肖恩一串加密后的数字。
具体规则是这样的，第一个删除，第二个数放到末尾
第三个数删除，第四个数放到末尾。
依次类推。删除的序列就是佩琪的QQ。

我们该怎么处理呢？
这就需要我们的队列了。
第一个也就是我们的head，记录队首。
末尾就是我们的tail，记录队尾。
第一个数删除，也就是模拟我们的出队。
第二个数放到最后，也就是模拟我们的入队。
此时我们的head 也就是第一个数，要向后移动head++，才能操作我们的第二个数，第二个数放到末尾，我们要tail++，才能操作我们第四个数就这样一次类推。

请看具体代码

队列
#include "stdio.h"
struct queue         //定义一个结构体，有头有尾有数组
{
	int a[100];
	int head;
	int tail;
};
int main()
{
	struct queue q;//定义结构体名称
	int i;
	q.head=1;     //对队列的头尾进行初始化
	q.tail=1;
	for(i=1;i<=9;i++) //输入数据，同时让尾部先达到改组数据的长度
	{
		scanf("%d",&q.a[q.tail]);
		q.tail++;
	}
	while(q.head<q.tail) //
	{
		printf("%d",q.a[q.head]);//输出头序列
	    q.head++;                 //出队
		q.a[q.tail]=q.a[q.head];//让第二个数去最后面
		q.tail++;               //最后一个位置加一
		q.head++;               //入队，变成第三个数
	}//为什么能循环成功呢？再一次循环中头加2，尾部只加1；
	return 0;
}

相信大家对队列已经有所了解了

3. 接着我们将用一道题来说一说bfs
   这道题的题目是肖恩找佩琪。
   肖恩的位置在（1，1）。
   佩琪的位置在（4，3）。
   我们希望用过最短路径找到佩琪。
   当然中间也会有一些障碍物。
   我们规定0可走，1不可走。
   地图如下
   0010
   0000
   0010
   0100
   0001

#include "stdio.h"
struct note //我们使用bfs怎么能少的了结构体呢，利用结构体进行出队与入队的操作，就像上面的例题一样
{
	int x;//x表示此时的横坐标
	int y;//y则是此时的纵坐标
	int s;//s就是我们走的步数
};//这里的结构体可和上面的不一样
//这一个结构体相当于上面数组的一个元素
//也就是说这里的一个机构体相当于队列中的一个元素

int main()
{
	int a[50][50]={0},book[50][50]={0};
	//第一个数组用来储存地图
	//第二个数组用来标记哪些点走过
	int i,j,k,p,q,m,n,x,y,tx,ty;
    struct note que[2501];//就是定义2500个结构体存放每一步
    //分别往四个方向行走
	int next[4][2]={{0,1},// right
	{1,0},//down
	{0,-1},//left
	{-1,0}};//up

	int head,tail;//结构体怎么能没有头和尾呢
	//不然怎么出队与入队
	

	int flag;//这个flag很巧妙，请看下面


	printf("input two number");
		scanf("%d%d",&n,&m);  //输入这个地图的行列


	printf("input  the  map"); //输入初始地图
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);

		printf("input the people address");
			scanf("%d %d %d %d",&x,&y,&p,&q);//这个当然是肖恩和佩琪的初始地址啦
	

        head=tail=1;//最开始队列里没啥东西就一个头和尾
        //我们要用尾对队列的下一步进行处理
        //比如尾部的s为2，下一步当然尾部的s为3。
        //这就需要把尾向下移一个。
		que[tail].x=x;
		que[tail].y=y;
		que[tail].s=0;
		tail++;//对尾部进行赋值以后，当然要把尾向后移动一个
	    book[x][y]=1;//最开始的点标记走过了


		//开始队列



		while(head<tail)//头一直小于尾
		// 这样可以迭代出我们想要的结果
		{

		    for(k=0;k<=3;k++)
			{

			    tx=que[head].x+next[k][0];//利用迭代走每一步
		        ty=que[head].y+next[k][1];//利用迭代走每一步，对照着那个next的数组你能明白的
		
			    if(tx<1||tx>n||ty<1||ty>m)//和我们dfs一样也要判断边界
			    continue;

			    if(a[tx][ty]==0&&book[tx][ty]==0)//我们能走下一步的前提
			    //这个点可以走a数组为0
			    //这个点没走过book数组为0
				{
					book[tx][ty]=1;//走过了当然要标记，不然走重复了
					que[tail].x=tx;
					//我们要对队列进行赋值呀
					que[tail].y=ty;
					que[tail].s=que[head].s+1;//这时的步数要比刚开始加一
					tail++;//和上面一样，移动一位，方便下次赋值
				}
				if(tx==p&&ty==q)
				{
					flag=1;//看flag就用在这
					//用flag标识满足条件
					break;
				}
			}
			if(flag==1)
				break;
			head++;
		}
		printf("%d",que[tail-1].s);
			return 0;

带入各个数值最后输出的值是7
如果我们用dfs加判断最短的条件输出的也是7。

由于篇幅有限就不给大家敲dfs的代码了。

希望大家能通过这一道例题明白bfs的基本含义

bfs就是一步一步尝试，不断试错，找到最佳！

------以上题目和代码出自《啊哈！算法》
我仅对部分代码坐了充分的补充和注释。