bfs与dfs

从大一就开始搞算法，结果到现在对这些的理解都还这么浅。。。

dfs（深度优先搜索）：这种算法最形象的描述就是不撞南墙不回头，不达到目的就一直往一个方向搜，实现算法使用的是递归，每到一个新的点就会有一些信息被更新，将这些更新后的信息作为参数传入下一层，如果一个方向的深搜出口不符合条件那么就回溯到上一个点，并且上一个点的信息仍然没有改变.，总结一下就是搜索深度优先，能深就不回去

bfs（广度优先搜索）：就和dfs是反着的，利用队列来实现，bfs优先搜索广度，就是把一个点的能到的所有点先确定了后再向深度进行搜索。

我们拿一个图来说明

如果用dfs来走，那么就像这样

这就是用dfs搜索的一条路径，可以看出，如果走一条路要用1分钟的话，那么用dfs走到终点的路径不一定是时间最短的。

1 void dfs(当前点)
2 {
3 if(达到条件) //递归出口
4 return ;
5 通过某种方法从当前点到下一个点tmp；
6 dfs(tmp);
7 }

再看看bfs

其中颜色相同的线表示他们所指目的地是同时检测的，当然我这里只画了左边的一半。这种情况下我们到达终点还是不能确保时间最短（但是如果利用优先队列就可以）。

void bfs(int start)
{
queueq;
q.push(start);vis[start]=1;//vis一般记录一下某个点有没有访问过，比如如果终点访问到了就结束，或者一个点访问了就不用访问
while(!q.empty())
{
int s=q.front();q.pop();
通过某种方式到下一个点next;
if(!vis[next])
{
q.push(next);
}
如果到达终点就结束
}
}

dfs和bfs我的理解还是不深，有时候不能搞清楚用哪个，因为有些时候两个用都可以，但有时候却只能用其中一个，或者其中一个简单，另一个十分复杂。

例题：poj3126，迷宫问题

dfs和bfs都可以找到起点到终点的路径，但只能找到存在性，如果有要求最优解那么就还要利用优先队列。

优先队列的bfs:顾名思义，就是在实现bfs的过程中用的是优先队列，优先队列可以对其中存储的结构的某些值进行自动的排序，依靠这个特点，在上面的例子中，我们可以拿结构体存每个点的信息（起点到这个点的时间和这个点的编号），存入优先队列时按照‘时间’从小到大，这样每次取出的第一个点到起点的时间都最短，如果这个点可以到终点，那么这个时间就是答案。

例题:poj2312 +代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

q;
vis[start.x][start.y]=1;
q.push(start);
while(!q.empty())
{
Point next,now;
now=q.top();q.pop();
for(int i=0;i<4;i++)
{
next.x=now.x+dir[i][0];next.y=now.y+dir[i][1];
if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m&&!vis[next.x][next.y]&&mp[next.x][next.y]!='R'&&mp[next.x][next.y]!='S')
{
int t1=1;
if(mp[next.x][next.y]=='B')
t1++;
vis[next.x][next.y]=1;
next.t=now.t+t1;
q.push(next);
if(next==fina)
{
printf("%d\n",next.t);
return ;
}
}
}
}
printf("-1\n");
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)&&(m+n))
{
memset(vis,0,sizeof(vis));
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='Y')
{
start.x=i;
start.y=j;
}
if(mp[i][j]=='T')
{
fina.x=i;fina.y=j;
}
}
BFS();
}
return 0;
}