正文
dfs和bfs的简单总结
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
首先是dfs,又名深度优先搜索。看名字就知道,它的核心思想就是一直搜索,先在一条路上面一路撸到底,如果到底没有办法前进了,那么判断是否到达终点,如果没有到达,那么就回溯到之前的点再撸。
dfs的要点:
1、考虑当下应该怎么做,在你现在的点上面你应该怎么做,可以怎么做。可以向上吗?可以向下吗?
2、后面的和前面一样的做。递归的思想。
3、要考虑边界,终点等题目给出的条件检测。过滤掉那些不需要的解。
4、利用适当的数据结构,保存当前点是否走过,保存走过的路线等。
模版:
void dfs(int step)
{
判断你的所有条件,如果不行直接return;
for(循环每一个方向)
{
dfs(step+1)
}
return;
}
map【】【】记录走过的地方,走过的记为1
可以尝试利用堆栈来存放记录
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>using namespace std;int result[];
int book[];
int r=;
/*求九个不同的个位数组合满足,3位+3位=3位的题目,主要是记录一下dfs的模版*/
void dfs(int step)
{
if(step == )/*简单的优化一下*/
{
int sum = result[]* + result[]* + result[]* + result[]* + result[] + result[]; if(book[sum%] == )
return; sum/=; if(book[sum%] == )
return; sum/=;
if(book[sum%] == )
return;
} if(step == )
{
if(result[]* + result[]* + result[]* + result[]* + result[] + result[] == result[]* + result[]* + result[])
{
printf("%d%d%d + %d%d%d = %d%d%d\n",result[],result[],result[],result[],result[],result[],result[],result[],result[]);
r++;
}
return;
} int i;
for (i = ; i <= ; i++)
{
if(book[i] == )
{
result[step] = i;
book[i] = ;
dfs(step+);
book[i] = ;
}
} return;
}int main()
{
clock_t start,finish;
double duration;
start = clock(); dfs();
cout<<"-------------------"<<r<<endl; finish = clock();
duration = double(finish - start)/CLOCKS_PER_SEC;
printf("time used:%f ms\n\n",*duration);
return ;
}
接下来是bfs,又名广度优先搜索,他是一个老实人,一步步走的很踏实,只有把n步的能走的地方走遍,才会走第n+1步,慢慢的拓展
要点:
1、用队列保存每一步走的结果,用一个字段去表示走的步数;
2、没有递归,利用while循环到最终结果;
3、时刻注意队列的首尾指针的位置;
模版:
while(head<tail)
{
for(循环所有方向)
{
把坐标进行改变,改成now的坐标,意思就是走一步
判断所有不可能的情况,不可能就continue
标记走过了
在队列中加入这个走过的点和步数
*****tail++*****
}
*****head++*****
}
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>using namespace std;/*首先定义方向数组*//*
X/Y 0/-1
-1/0 0/0 1/0
0/1
右下左上*/int way[][] = {
{,},//右
{,},//下
{-,},//左
{,-}//上
};
int map[][];
int book[][];
int n,m;
int head=;
int tail=;
int flag=;struct que
{
int x;
int y;
int stpe;
};struct que q[];int main()
{ int x,y;
cin>>n>>m;
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
cin>>map[i][j];
}
} head = ;
tail = ; q[tail].x = ;
q[tail].y = ;
q[tail].stpe = ;
tail++; book[][] = ;
flag = ; while (head<tail)
{
for (int i = ; i < ; i++)
{
x = q[head].x + way[i][];
y = q[head].y + way[i][]; if(x< || y < || x > n || y > m)
continue;
if(map[x][y] == && book[x][y] == )
{
q[tail].x = x;
q[tail].y = y;
q[tail].stpe = q[head].stpe + ;
tail++;
book[x][y] = ; } if(x == && y == )
{
printf("--------------------%d\n",q[tail-].stpe);
return ;
}
}
head++;
} return ;
}
主要是记录一下两钟搜索的模版,具体两种搜索的使用还要在实际中进行检验,对于迷宫的题目只是现在肯定不会迷茫了,之后对于图的遍历还有别的,对于两种搜索的比较取舍,之后再写吧。