前言：原本是应该做一整个图论专题的，但是本蒟蒻能力有限，再加上深搜广搜忘得差不多了，所以这篇就专门复习一下bfs和dfs.
一、DFS(深搜)
Depth First Search，深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，每次都尝试向更深的节点走（即一条路走到黑）。
总体来说，递归可以很好地实现dfs,但也体现了dfs的低效性，在正式解题的过程中我们可以通过剪枝，特判等方式提高效率。
模板：
void dfs()
{
if(到达终点状态) {
...//根据题意添加
return;
}
if(越界或者是不合法状态) return;
for(扩展方式) {
if(扩展方式所达到状态合法) {
修改操作;//根据题意来添加
标记；
dfs（）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}
}
} 例题一：经典迷宫问题? POJ-3984
?解析：定义一个二维数组：?
int m[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求找出从左上角到右下角的最短路线。
即给你一个地图，让你在地图中找出最短的路径。可以开两个队列记录走过的路径，并用vis数组记录该点是否访问过。当然这题用bfs有更合适的解法，后面会写到。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int m[10][10];
int vis[10][10] = {0};
const int p[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//直线移动
int flag;
queue<int> c1,c2;//记录路径(x,y)
void dfs(int x,int y)
{
if(x==4&&y==4)
{
c1.push(x);
c2.push(y);
flag = 1;
return;
}
else if(x > 4 || y > 4 || x < 0 || y < 0)//越界
return;
if(m[x][y] == 0 && !vis[x][y])
{
c1.push(x);
c2.push(y);
vis[x][y] = 1;//标注已访问
for(int i=0;i<=4;i++)
{
x += p[i][0];
y += p[i][1];
dfs(x,y);
if(flag) break;
}
}
}
int main()
{
flag = 0;
for(int i=0;i<=4;i++)
{
for(int j=0;j<=4;j++)
{
scanf("%d",&m[i][j]);
}
}
dfs(0,0);
while(!c1.empty())
{
printf("(%d,%d)\n",c1.front(),c2.front());//按顺序输出最短路径的坐标
c1.pop();
c2.pop();
}
return 0;
}
例题二：经典八皇后问题
即如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
解析：此问题涉及回溯法，即先确定第一个皇后棋子的位置，再尝试将剩余棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。我们从第一行开始搜索，用for循环来确定每一列,用mp数组标记位置，对每一个坐标进行检验(左上，单列上方，右上是否有棋子)。接着输出每一种排法。
下面给出原始八皇后问题的解法（dfs+回溯）
#include<iostream>
using namespace std;
int t=1,;
int mp[8][8]={0};
void print()
{
printf("%d:\n",t++);
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
printf("%d ",mp[i][j]);
}
cout<<endl;
}
}
int check(int x,int y)
{
int a=x;
for(int i=1;i<8;i++)
{
if(x-i>=0&&y-i>=0&&mp[x-i][y-i])//检查左上
return 0;
}
while(a>0) //检查上方
{
a--; //注意这地方要用a代换x来进行递减，否则x的值将带入下个循环
if(mp[a][y]) return 0;
}
for(int j=1;j<8;j++)
{
if(x-j>=0&&y+j<8&&mp[x-j][y+j]==1)//检查右上
return 0;
}
return 1;
}
void dfs(int k)//从第一行开始搜索
{
if(k==8) //找到一种方法
{
print();
return;
}
for(int i=0;i<8;i++)
{
if(check(k,i)) //递归公式
{
mp[k][i]=1;
dfs(k+1);//每行最多放一个
mp[k][i]=0;
}
}
}
int main()
{
dfs(0);
return 0;
}
?二、BFS（广搜）?
Breadth First Search，广度优先搜索，就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。这样做的结果是，BFS 算法找到的路径是从起点开始的?最短?合法路径。换言之，这条路所包含的边数最小。在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。
还是先看迷宫问题，用BFS搜索的基本思路为：按步数搜索，也就是我们从起点开始，找到这个点的所有可能走到的点,并把每一步的路径存储，然后再寻找它下一步能走到的点，一直循环重复直到找到终点，那就是从起点能到终点的最短路径了。
#include<iostream>
using namespace std;
int a[5][5];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int front=0,rear=1;//头尾指针
struct node
{
int x,y,pre;
}q[100];//记录路径，pre指向前一个结点
void print(int i)
{
if(q[i].pre!=-1)
{
print(q[i].pre);
cout<<"("<<q[i].x<<", "<<q[i].y<<")"<<endl;
}
}
void bfs(int x1,int y1)
{
q[front].x=x1;
q[front].y=y1;
q[front].pre=-1;
while(front < rear)
{
for(int i=0; i<4; i++)
{
int xx = dx[i] + q[front].x;
int yy = dy[i] + q[front].y;
if(xx<0||xx>=5||yy<0||yy>=5||a[xx][yy])//越界或已走过
continue;
else
{
a[xx][yy]=1;
q[rear].x=xx;
q[rear].y=yy;
q[rear].pre=front;
rear++;
}
if(xx==4&&yy==4) print(front);
}
front++;
}
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&a[i][j]);
cout<<"(0, 0)"<<endl;
bfs(0,0);
cout<<"(4, 4)"<<endl;
}
例题：HDU1548?A strange lift
题意：电梯在每一层都有一个数t，只能往上或者往下t层。求从a层到b层至少需要按多少次电梯按钮。
using namespace std;
int n,a,b;
map<int,int>mp;
int ans=inf;int f[200005];
void dfs(int id,int step)
{
if(id<1||id>n)
return;
if(id==b)
{
ans=min(ans,step);
return;
}
if(step>=f[id])//剪枝
return;
f[id]=step;
dfs(id+mp[id],step+1);
dfs(id-mp[id],step+1);
return;
}
int main()
{
while(scanf("%d",&n)&&n)
{
mp.clear();
scanf("%d%d",&a,&b);
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
mp[i]=t;
f[i]=inf;
}
ans=inf;
dfs(a,0);
if(ans==inf)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}三.总结
总体来说，bfs与dfs是基础且易掌握的。了解两种算法的适用范围对于解题很有帮助。在DFS中我们说关键点是递归以及回溯，在BFS中，关键点则是状态的选取和标记。
1.数据结构上的运用
DFS用递归的形式，用到了栈结构，先进后出。
BFS选取状态用队列的形式，先进先出。
2.复杂度
DFS的复杂度与BFS的复杂度大体一致，不同之处在于遍历的方式与对于问题的解决出发点不同，DFS适合目标明确，而BFS适合大范围的寻找。
3.思想
思想上来说这两种方法都是穷竭列举所有的情况。