在信息学中，有两种基础的搜索算法，它们分别为--DFS与BFS（深搜与广搜）。
DFS
DFS（Depth First Search）深度优先算法，是一种用于遍历或搜索树或图的算法，也可用于统计路径数量和解决全排列问题等。
DFS会在搜索时以深度为主，在一条路径到头后再次回溯，寻找其他路径。
核心思想
DFS的核心思想为递归和回溯
递归
递归通俗来讲就是一个函数自己调用自己
举个例子：P5739 【深基7.例7】计算阶乘
普通解法：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=1;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
ans*=i;
}
cout<<ans;
return 0;
}递推解法：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=17;
int n;
ll f[N];
int main(){
cin>>n;
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]*i;
}
cout<<f[n];
return 0;
}
递归解法：
#include<bits/stdc++.h>
using namespace std;
int jc(int x){
if(x==1)return 1;
return x*jc(x-1);
}
int a;
int main(){
cin>>a;
cout<<jc(a);
return 0;
}递归图：
在递归中，一个问题会被分解为一个又一个更小的问题，直到到达基准情况（比如此题中的return 1），在到达基准情况后，又会一层一层的向回回返，这个过程就叫做回溯。
回溯
举一个经典的例子：
从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“太困了不讲了”，于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。
写成代码就是：
#include<bits/stdc++.h>
using namespace std;
void cq(int x){
cout<<"从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“";
if(x==1){
cout<<"太困了不讲了";
return;
}
cq(x-1);
cout<<"于是都回去睡觉了。”";
return;
}
int main(){
cq(4);
}"于是都回去睡觉了。”"就是代码的回溯部分。
DFS执行过程
DFS的执行过程如下：
c++模板：
#include<bits/stdc++.h>
using namespace std;
void DFS(参数){
if(跳出条件){
执行语句;
return;
}
标记语句;
for(遍历){
if(判断状态合法)continue;
标记;
DFS(参数);
取消标记;
}
}
int main(){
DFS(参数);
return 0;
}DFS举例
以下以洛谷原题P1596 [USACO10OCT] Lake Counting S为例：
洛谷题面：
c++代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int tc=0;
int mov[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}};//移动数组
int ma[105][105];//地图
void print(){//输出测试
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
cout<<setw(6)<<ma[i][j];
}
cout<<endl;
}
}
void dfs(int x,int y){
if(x>n||y>m||x<1||y<1||ma[x][y]!=0){//判断越界和已访问
return;
}
ma[x][y]=tc;//标记
for(int i=0;i<8;i++){//遍历位置
int dx=x+mov[i][0];
int dy=y+mov[i][1];
dfs(dx,dy);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){//转化地图
cin>>s;
for(int j=1;j<=m;j++){
string b;
b=s[j-1];
if(b=="w"){
ma[i][j]=0;
}
if(b=="."){
ma[i][j]=-1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ma[i][j]==0){//找到新水坑
tc++;//增加水坑数
dfs(i,j);//开始深搜水坑范围
}
}
}
cout<<tc;//输出水坑数
// print();
return 0;
}
推荐题目：
P1123 取数游戏(需要一些特殊方法)
P1219 [USACO1.5] 八皇后 Checker Challenge(需要数组判断斜行)
P6207 [USACO06OCT] Cows on Skates G(路径存储)
如果这些你都会的话，可以挑战一些较难题：
P2919 [USACO08NOV] Guarding the Farm S
BFS
BFS(Breadth First Search)广度优先算法除了遍历以及搜索之外，还可以用来搜索最短路。
BFS会同时拓展所有处在同一批次的路径。
核心思想
BFS主要依靠于队列，将同一批次的点同时扩大，可以用来搜索最短路。
执行过程
执行过程如下：
c++模板：
#include<bits/stdc++.h>
using namespace std;
queue<类型> q;
int main() {
执行语句;
while(!q.empty()){
获取位置;
q.pop();
if(判断越界)continue;
for(位置遍历){
获取新位置;
if(跳过条件)continue;
标记;
q.push(新位置);
}
}
return 0;
}以下以洛谷原题P1443 马的遍历为例：
洛谷题面：
c++代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
int k[405][405];
int mov[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};//移动数组
struct hou{//存储位置结构体
int a,b;
};
queue<hou>q;//队列
int main() {
cin >>n>>m>>sx>>sy;//输入
memset(k, -1, sizeof(k));//初始化
q.push({sx,sy});//初始位置压入队列
k[sx][sy]=0;//初始位置
while(!q.empty()){//判空队列
int x=q.front().a;
int y=q.front().b;
q.pop();//弹出
if(x>n||x<1||y>m||y<1)continue;//判断越界
for(int i=0;i<8;i++){//遍历移动位置
int ux=x+mov[i][0];
int uy=y+mov[i][1];
if(k[ux][uy]!=-1||ux>n||ux<1||uy>m||uy<1)continue;//判断非法和已走位置
k[ux][uy]=k[x][y]+1;//标记
q.push({ux,uy});//压入新位置
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<k[i][j]<<" ";//输出
}
cout<<endl;
}
return 0;
}
推荐题目：
总之，DFS和BFS都十分重要，并且可以用来支撑图论和树。
点个赞吧
