简介
深度优先搜索算法\(（Depth First Search，\) 简称 \(DFS）：\) 一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 \(v\) 的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点 \(v\) 的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为 \(O(!n)\)。
基本思想
1.为了求得问题的解，先选择某一种可能情况向前探索；
2.在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；
3.如此反复进行，直至得到解或证明无解。
操作步骤
有这么一幅图，我们需要知道：求图中的 \(V0\) 出发，是否存在一条路径长度为 \(4\) 的搜索路径。
搜索过程如下：
具体代码实现为：（只展示部分代码）
bool DFS(Node n, int d){ //n代表着是当前节点 ，d表示走的次数
if (d == 4){//路径长度为返回true，表示此次搜索有解
return true;
}
for (Node nextNode in n){//遍历跟节点n相邻的节点nextNode，
if (!visit[nextNode]){//未访问过的节点才能继续搜索
//例如搜索到V1了，那么V1要设置成已访问
visit[nextNode] = true;
//接下来要从V1开始继续访问了，路径长度当然要加
if (DFS(nextNode, d+1)){//如果搜索出有解
//例如到了V6，找到解了，你必须一层一层递归的告诉上层已经找到解
return true;
}
//重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中
visit[nextNode] = false;
}
//到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。
}
return false;//本次搜索无解
}
例题
学算法当然要刷题领悟啦，不然就是这种一看就会(只是背了下来)，一写就废的,下面就让我们一起看看这个俗称不撞南墙不回头算法都有哪些例题！！！
排列问题
#include<bits/stdc++.h>
using namespace std;
int n;
int ans[15];//保存当前的方案
int use[15];//表示每个数是否被用过
void dfs(int x){//X表示当前搜索到那个数
if(x>n){//如果N位都搜索完了，就输出方案并返回
for(int i=1;i<=n;i++)
printf("% 5d",ans[i]);//输出方案
puts("");
return;
}
for(int i=1;i<=n;i++)//从小到大枚举
if(!use[i]){//判断这个数是否用过
ans[x]=i;//保存到方案中
use[i]=1;//标记这个数被使用了
dfs(x+1);//进行下一步搜索
use[i]=0;//撤销标记
}
}
int main()
{
scanf("%d",&n);//输入
dfs(1);//从第一个数开始搜索；
}