我记得前言第一次接触DFS是在去年的3月或4月。 当时也在准备比赛的时候听说DFS很重要，然后去谷歌教了我什么是DFS。 当时的我才刚刚开始学习C，还没有学习数据结构。 说实话，当时我明白了算法的原理，但对什么图和树完全不懂。 后来学习了数据结构之后，对DFS的原理也相当了解，但没有总结过。 今天主要进行DFS的算法进行简单的自我总结。 一个是为比赛做准备，另一个应该从现在开始正式采取数据结构。 (请原谅我花了半年去网页开发。
——————————3——3——3——3333————3——--以上内容并不重要(是我自己的抱怨)
你第一次知道DFS是什么？ 是Depth First Search英语的缩写，翻译为“深度优先检索”。
从名字可以看出，DFS主要是检索算法，根据深度优先方式
深度优先搜索算法(Depth-First-Search，简称DFS )是一种用于遍历和搜索树或图的算法。 沿着树的深度穿越树的节点，尽可能深入地探索树枝。 如果自己搜索到节点v的某一边，则搜索会追溯到发现节点v的边的开始节点。 此过程将持续到找到所有可从源节点访问的节点为止。 如果存在尚未发现的节点，则选择任一个作为源节点，重复上述过程，直到所有节点被访问为止。 属于盲目搜索。
主要思想：不撞南墙，不回头。
深度优先遍历的主要思想是首先将未访问的顶点作为开始顶点，沿当前顶点的边前往未访问的顶点。如果没有未访问的顶点，则返回上一个顶点，继续探索访问其他顶点，直到访问了所有顶点。
沿着一条路径扫描到末端，从那里开始，又沿着另一条路径进行同样的扫描，直到所有顶点都被访问。
【以上引用来自维基百科】
小结：
深度优先搜索——类似于树根扫描，是树根扫描的推进
简述算法的过程
1、以任意顶点为起点v，访问该顶点2，沿深度方向依次扫描v的未访问邻接点——，直到本次扫描结束为止3、1次扫描结束时，有未访问顶点时：以任意的未访问顶点为起点。 GOTO第二步算法是递归伪代码演示
DFS(dep，)//dep找到当前DFS的深度(if ) )解||无法前进)、//在此进行相应操作的返回； }列举以下情况： DFS(dep1，) } 递归伪代码演示(稍详细一点，其实相同) ) )。
bool visited[MAXNODE]； //顶点的访问标识符数组voidDFSinit(graphg ) for ) I=0； iG.VertexNum； I ) { visited[i]=false； }voidDFS(graphg，int v ) { //v:顶点阵列的编号Visit[v]； visited[v]=true； w=firstadj(g，v )； //返回： v的第一个相邻点，0是无相邻点while(w！=0) if (！ visited[w]{DFS(g，w )； //参数传递w-v}w=nextadj(g，v，w )； //返回： v的邻点w之后的邻点，0表示不存在}} DFS遍历——图解过程
注：
存储结构不确定，且遍历结果不是唯一的DFS序列。 DFS(g，v1 )=) v1、v2、v3、v6、v5、v7、v4、v8、v9 )小结
从图解和二维码中可以看出，DFS其实就是找一条路线，一直走(深度优先)，直到满足条件(这是运气好)，或者走投无路，去不成了(撞到南墙)。 如果找不到合适的结果状态，则后退一步(追溯)，继续下一步寻找路径，碰到后再追溯，直到找到目标状态或所有情况都被遍历为止，程序结束
DFS递归算法框架/*此DFS框架以2D坐标范围为例，体现了DFS算法的实现思想。 *.# include cstdio # include cstring # includecstdlibusingnamespacestd； const int maxn=100； bool vst[maxn][maxn]； //访问标记int map[maxn][maxn]； //坐标范围int dir [4] [2]={ 0，1，0，- 1，1，0，- 1，0 }； //方向向量，(x，y )周围的四个方向boolcheckedge(intx，int y )//判断边界条件和约束(if (！ VST[x][y].//满足条件的return 1； 与else //约束的冲突
return 0;}void dfs(int x,int y){ vst[x][y]=1; // 标记该节点被访问过 if(map[x][y]==G) // 出现目标态G { ...... // 做相应处理 return; } for(int i=0;i<4;i++) { if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点 dfs(x+dir[i][0],y+dir[i][1]); } return; // 没有下层搜索节点，回溯}int main(){ ...... return 0;}【此框架引用自BFS和DFS算法原理（通俗易懂版）】
DFS递归算法实例讲解我一直都认为，对于我们学习技术的学生来说，想要了解一门技术或者一个知识点的，最好的方法是“在理解了理论知识的基础上进行实践”，实践才是检验真理的唯一标准，同时这种实践的方式学习知识点，才是印象最深刻，同时也是提高学习激情和欲望的有效方式。
话不多说，我们进入实战阶段。
原题我记不清了，这边就简单的说下题意
【题目】在给定的一个二维数组中找寻从起点（0，0）开始走，能到达哪些区域（真不记得题意了，大家自行脑补吧）
0 0 1 1 01 0 0 1 11 1 0 0 01 0 0 1 10 0 1 0 0我们假设上边就是输入数据（嘻嘻，将就一下），‘0’代表能够走的，‘1’代表不能走的，可以理解为墙，同时只能在所给的地图上走，也就是不能跳出去再调回来，求解区域
相信大家对于这个问题其实已经很明确了，其实就和“八连块”问题是一个道理的
【分析】我们从起点开始走，一直沿着一条路走，一直走到最后走不动的时候，进行回溯，再找寻下一条路线，直到最后没有路走，回到了起点位置（大家可以想想为什么会回到起点位置）结束。我们走过的地方其实就是题目的答案
源代码
我建议先自己实现一波后再来看哟。
#include <iostream>#include <cstring>#define N 10using namespace std;int dir[4][2] = {0,1,0,-1,1,0,-1,0};int vst[N][N]; //标记数组 int map[N][N]; //给定图 bool checkEdge(int x,int y);void dfs(int x,int y);int main(){ int n; cin>>n; memset(vst,0,sizeof(vst)); //初始化 memset(map,-1,sizeof(map)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>map[i][j]; //输入图 } } dfs(0,0); //进行DFS for(int i=0;i<n;i++){ for(int j=0;j<n;j++){// cout<<vst[i][j]<<" "; if(vst[i][j] == 6){ //找寻到的结果， cout<<"i:"<<i<<" j:"<<j<<endl; } } cout<<endl; } return 0;}bool checkEdge(int x,int y){ //检验当前点是否可走 if(vst[x][y]==0 && map[x][y]==0 && x>=0 && x<55 && y>=0 && y<5){ return true; } return false;}void dfs(int x,int y){ vst[x][y] = 6; for(int i=0;i<4;i++){ if(checkEdge(x+dir[i][0],y+dir[i][1])){ dfs(x+dir[i][0],y+dir[i][1]); } } return;} 参考 BFS和DFS算法原理（通俗易懂版）深度优先搜索-维基百科