深度优先搜索（DFS）和广度优先搜索（BFS）
自己对于这块地方还是有点忘，而且后面要经常用到搜索，所以整理一下。
搜索真的是个很神奇的东西，通过代码的变化就能解决许许多多种的实际问题。
一、深度优先搜索(Depth First Search)，重在追求”专一”吧!一条道走到黑，
主要是递归思想。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的
邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个
未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
一般默认遍历时先遍历节点编号小的
（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8
（2）从stack中访问栈顶的点
（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；
（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；
（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
我们以SDUTOJ此专题第一题为例
https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2717/pid/2107
#include<bits/stdc++.h>
using namespace std;
int MAP[100][100];//邻接矩阵表示的图
int vis[100];//标记数组
int k,m;
void DFS(int n)
{
if(n==0)
{
cout<<n;
}else
{
cout<<' '<<n;
}
vis[n]=1;
for(int i=0;i<k;i++)//注意看你建的图是从0开始还是从1开始
{
if(vis[i]==0&&MAP[n][i]==1)//如果i点还未访问并且这形参 n 和 i 连通那么就应该顺着递归下去
{
DFS(i);
}
}
}
int main()
{
int T,u,v;
cin>>T;
while(T--)
{
memset(MAP,0x3f3f3f,sizeof(MAP));//注意初始化
memset(vis,0,sizeof(vis));
cin>>k>>m;//k是顶点数,m是边的条数
for(int i=0;i<m;i++)
{
cin>>u>>v;
MAP[v][u]=MAP[u][v]=1;
}
DFS(0);//我的图是从0开始建的，你们可以根据个人喜好来
cout<<endl;
}
return 0;
}
对了第二题要还要输出遍历完之后返回原点的节点顺序，其实只需要另一个数组来存就行，递归函数加两句话就行
void dfs(int s)
{
vis[s]=1;
j[w++]=s;
for(int i=0; i<n; i++)
{
if(vis[i]==0&&MAP[s][i]==1)
{
dfs(i);
j[w++]=s;
}
}
}
二、广度优先搜索（用的最广泛）
广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历算法。这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。
一般用队列来辅助实现BFS算法。
具体思想：从图中某顶点a出发，在访问了a之后依次访问a的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
若我们要进行广度优先搜索的遍历并输出
邻接矩阵的实现为
#include<bits/stdc++.h>
using namespace std;
int MAP[105][105];
int vis[105];
int n,m;
void bfs(int s)//传入起点
{
queue<int>q;//要通过队列来辅助
q.push(s);
vis[s]=1;
int flag=0;
while(!q.empty())//若队列不空，就意味着还没搜索完
{
int k=q.front();//每次以队头为基准，寻找和它相连的点
q.pop();//注意每次把队头取出来
if(flag==0)
{
cout<<k;
flag=1;
}else
{
cout<<" "<<k;
}
for(int i=0;i<n;i++)
{
if(MAP[k][i]==1&&vis[i]==0)//若这个点没有被访问过并且连通就以进行入队操作从而进一步搜索
{
q.push(i);
MAP[k][i]=MAP[i][k]=0;
vis[i]=1;
}
}
}
}
int main()
{
int u, v, s, t;
cin >> t;
while(t--)
{
memset(MAP,0,sizeof(MAP));
memset(vis,0,sizeof(vis));
cin>> n >> m >> s;
for(int i = 0; i < m; i++)
{
cin >> u >> v;
MAP[u][v]=MAP[v][u]=1;
}
bfs(s);
}
return 0;
}
邻接表的实现为
#include<bits/stdc++.h>
using namespace std;
vector<int>MAP[105];//借助vector来实现邻接表
int vis[105];
int n,m;
void bfs(int s)
{
int flag=0;
vis[s] = 1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int k=q.front();//每次以队头为基准，寻找和它相连的点
q.pop();
if(flag==0)
{
cout<<k;
flag=1;
}else
{
cout<<" "<<k;
}
int len = MAP[k].size();
for(int i = 0; i < len; i++)
{
if(!vis[MAP[k][i]])//若这个点没有被访问过并且连通
{
q.push(MAP[k][i]);
vis[MAP[k][i]] = 1;
}
}
}
}
int main()
{
int u, v, s, t;
cin >> t;
while(t--)
{
for(int i = 0; i < 105; i++)
{
MAP[i].clear();//注意清空
}
cin>> n >> m >> s;
for(int i = 0; i < m; i++)
{
cin >> u >> v;
MAP[u].push_back(v);
MAP[v].push_back(u);
}
bfs(s);
}
return 0;
}
BFS还可以用来做具体的地图搜索题，以此专题H - 找朋友为例
https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2717/pid/2779
#include<bits/stdc++.h>
using namespace std;
char MAP[20][20];
int vis[20][20];
int d[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int n,m;
struct node
{
int x;
int y;
int time;
};
void bfs(int x,int y)
{
queue<node>q;
node t;
t.x=x;
t.y=y;
t.time=0;
q.push(t);
vis[x][y]=1;
while(!q.empty())
{
node k=q.front();
q.pop();
if(MAP[k.x][k.y]=='Y')
{
cout<<k.time<<endl;//若找到终点则输出所用时间（步数）并结束
return ;
}
for(int i=0; i<4; i++)
{
t.x=k.x+d[i][0];
t.y=k.y+d[i][1];
if(t.x>=0&&t.x<n&&t.y>=0&&t.y<m&&vis[t.x][t.y]==0&&MAP[t.x][t.y]!='#')//如果这点未越界并且这点可以走（不是墙），那么就可以进行入队从而进行进一步的搜索操作
{
t.time=k.time+1;
vis[t.x][t.y]=1;
q.push(t);
}
}
}
cout<<-1<<endl;
}
int main()
{
int i,j;
while(cin>> n >> m)
{
memset(vis,0,sizeof(vis));
for(i = 0; i <n; i++)
{
cin>>MAP[i];
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(MAP[i][j]=='X')//若找到起点，则带着坐标break出去
{
break;
}
}
if(j<m)
{
break;
}
}
bfs(i,j);//从起点开始遍历
}
return 0;
}
总结
一般来说，
广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是”搜到就是最优解”
而深搜用于找多个解或者是”步数已知（好比3步就必需达到前提）”的标题，
它的空间效率高，然则找到的不必定是最优解，必需记实并完成全数搜索
像搜索最短路径这些的很显著是用广搜，因为广搜的特征就是一层一层往下搜的，保证当前搜到的都是最优解
深搜的实现近似于栈，
广搜则是操作了队列，边进队，边出队。
优缺点：
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高
题型归类
坐标类型搜索 ：这种类型的搜索题目通常来说简单的比较简单，复杂的通常在边界的处理和情况的讨论方面会比较复杂，分析这类问题，我们首先要抓住题目的意思，看具体是怎么建立坐标系（特别重要），然后仔细分析到搜索的每一个阶段是如何通过条件转移到下一个阶段的。确定每一次递归（对于DFS）的回溯和深入条件，对于BFS，要注意每一次入队的条件同时注意判重。要牢牢把握目标状态是一个什么状态，在什么时候结束搜索。还有，DFS过程的参数如何设定，是带参数还是不带参数，带的话各个参数一定要保证能完全的表示一个状态，不会出现一个状态对应多个参数，而这一点对于BFS来说就稍简单些，只需要多设置些变量就可以了。
数值类型搜索：这种类型的搜索就需要仔细分析分析了，一般来说采用DFS，而且它的终止条件一般都是很明显的，难就难在对于过程的把握，过程的把握类似于坐标类型的搜索（判重、深入、枚举），注意这种类型的搜索通常还要用到剪枝优化，对于那些明显不符合要求的特殊状态我们一定要在之前就去掉它，否则它会像滚雪球一样越滚越大，浪费我们的时间 。