深度优先搜索(DFS)与广度优先搜索(BFS)简单实现

１．深度优先搜索原理（以二叉树为例）

如下二叉树图（出处见水印）

通俗讲也就是一根筋冲到底，到底之后在找离自己最近的分叉口再一根筋到底，如此反复．

利用栈的原理对之前的节点进行存储，先入后出，即一路到底后便拿出栈中的最后一个数，反复进行．

栈的实现利用简单的迭代可便捷实现．

２．广度优先搜索原理（以二叉树为例）

如下二叉树图

再通俗讲也就是一层一层一层搜索，好比人的辈分，也就是先看祖爷爷辈的人，再看爷爷辈的人，再看爸爸辈的人，再看自己这一辈的人．

利用队列的原理对节点进行存储，先入先出．即首先将祖爷爷辈的人放入队列，将队列里的每个人的子辈加入新的队列．反复进行．

３．DFS与BFS的简单应用（以矩阵迷宫为例）

不多说，直接上代码，知道原理的话，看看代码看看注释就能懂了．

#include"stdio.h"
#include"math.h"
#include"string.h"
char gong[6][6]=
{
	'0','1','0','0','1','0',
	'0','0','1','0','0','0',
	'1','0','0','0','1','0',
	'0','0','1','0','1','0',
	'0','1','1','0','1','0',
	'0','0','1','0','0','0'
};                                        //定义一个６＊６的迷宫矩阵，０为可走路径，１为墙
int team[10][2],t=0,cop[10][2],coco=0;    //team[][0]储存行位，team[][1]储存列位，cop[][]同理                   

void show()                                //清屏并输出迷宫状态
{
	system("clear");    //Linux　清屏
	//system("cls");     //windows　清屏
	int n,m;
	printf("**********************\n");
	for(n=0;n<6;n++)
	{
		for(m=0;m<6;m++)
			printf("%c ",gong[n][m]);
		printf("\n");
	}
}

void copy()                            //将team[][]栈中的数据复制到cop[][]中，释放team[][]
{
	int n,m;
	for(n=0;n<t;n++)
	{
		cop[n][0]=team[n][0];
		cop[n][1]=team[n][1];
	}
	coco=t;
	t=0;

}

void depth(int a,int b,int c,int d)    //深度优先搜索的迭代函数
{
	char ce;
	show();
	gong[a][b]='*';
	ce=getchar();
	if(a==c&&b==d){return;}
	if(a>0)
		if(gong[a-1][b]=='0')//符合要求则说明该路线还有位置可以走，所以迭代深入.以下同理
			depth(a-1,b,c,d);
	if(a<5)
		if(gong[a+1][b]=='0')
			depth(a+1,b,c,d);
	if(b>0)
		if(gong[a][b-1]=='0')
			depth(a,b-1,c,d);
	if(b<5)
		if(gong[a][b+1]=='0')
			depth(a,b+1,c,d);
	return;
}

int main()
{
	int start[2],end[2],n,m,num,a,b,key=0,step=0,choice;
	char c;
	scanf("%d,%d %d,%d",&start[0],&start[1],&end[0],&end[1]);//输入开始位置和终点

	if(gong[start[0]][start[1]]=='1'||gong[end[0]][end[1]]=='1')//判断输入点是否正确
		{printf("error!!\nProgram Suspension\n");return 0;}
	a=start[0];
	b=start[1];
	gong[a][b]='*';
	t=1;
	team[0][0]=a;
	team[0][1]=b;
	printf("1.Breadth search\n2.Depth search\nYour choice:");//选择１为广度优先搜索，选择２为深度优先搜索
	scanf("%d",&choice);
	if(choice==1)
		while(1)
		{
			show();
			copy();
			for(n=0;n<coco;n++)
			{
				a=cop[n][0];
				b=cop[n][1];
				gong[a][b]='*';
				if(a==end[0]&&b==end[1]){key=1;break;}　//当到达终点，则直接退出循环，得到路径最小值
                                                //对４个方向是否存在可前进的位置进行判断，如果存在位置则存入team中
				if(a>0)
					if(gong[a-1][b]=='0'){team[t][0]=a-1;team[t++][1]=b;}
				if(a<5)
					if(gong[a+1][b]=='0'){team[t][0]=a+1;team[t++][1]=b;}
				if(b>0)
					if(gong[a][b-1]=='0'){team[t][0]=a;team[t++][1]=b-1;}
				if(b<5)
					if(gong[a][b+1]=='0'){team[t][0]=a;team[t++][1]=b+1;}
			}
			step++;        //计算步数
			if(key==1)break;
			c=getchar();                //此处利用getchar()函数达到可以通过按下回车键观察矩阵的一步步变化
		}
	else
		depth(start[0],start[1],end[0],end[1]);
	if(choice==1)
	{
		c=getchar();
		show();
		printf("Success!!\nThe minimum number of steps is %d\n",step);
	}
	else
	{
		show();
		printf("Success!!\n");
	}
	return 0;
}