【DFS】深度优先搜索递归方式讲解

　

dfs

前言

记得第一次接触到DFS还是在去年大概三四月份，当时也是在准备比赛的时候听说DFS很重要（原谅我是个小白），然后就去Google了一波什么叫做DFS，当时的我刚开始学习C++，还没有学习数据结构，讲道理当时我看懂了算法原理，但是对于什么图呀，树呀的还真是一窍不通。后边学习了数据结构后，对于DFS原理也是相当的了解（自我感觉），但从来没有总结过，今天主要是进行DFS的算法进行简单的自我总结，一是准备比赛，二是也应该从现在开始正式的拿起数据结构了（原谅我花了半年时间搞web开发去了）。

———————————————- 以上内容不重要（纯属我自己发牢骚）

初识DFS

什么是DFS？depth First Search英文的缩写，翻译过来就是“深度优先搜索”。

从名字上我们可以大概的看出，DFS主要是一种搜索算法，按照深度优先的方式

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

主要思想：不撞南墙不回头。

深度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问。

沿着某条路径遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。

【以上引用来自维基百科】

小结：

深度优先搜索——类似于树的先根遍历，是树的先根遍历的推广

简述算法过程

• 1、任选一顶点作始点 v ，访问该顶点
• 2、沿深度方向，依次遍历 v 的未访问邻接点——直到本次遍历结束
• 3、一次遍历完时，若有未访问顶点：任选一个未访问顶点作起始点，GOTO第二步

算法演示

递归伪代码演示

DFS(dep,、、、）        //dep代表目前DFS的深度
{
    if(找到解 || 走不下去){
        、、、     //在此处进行相应的操作
        return ;
    }
    枚举下一种情况，DFS（dep+1,、、、）
}

递归伪代码演示（稍微详细点，其实都是一样的）

bool visited[MAXNODE];      //顶点的访问标识数组
void DFSInit(Graph G){
    for(i=0; i<G.VertexNum; i++){
        visited[i] = false;
    }
}

void DFS(Graph G,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>
#include<cstdlib>
using namespace std;
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)周围的四个方向

bool CheckEdge(int x,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 0
1 0 0 1 1
1 1 0 0 0
1 0 0 1 1
0 0 1 0 0

我们假设上边就是输入数据（嘻嘻，将就一下），‘0’代表能够走的，‘1’代表不能走的，可以理解为墙，同时只能在所给的地图上走，也就是不能跳出去再调回来，求解区域

相信大家对于这个问题其实已经很明确了，其实就和“八连块”问题是一个道理的

【分析】我们从起点开始走，一直沿着一条路走，一直走到最后走不动的时候，进行回溯，再找寻下一条路线，直到最后没有路走，回到了起点位置（大家可以想想为什么会回到起点位置）结束。我们走过的地方其实就是题目的答案

源代码

我建议先自己实现一波后再来看哟。

#include <iOStream>
#include <cstring>
#define N 10
using 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算法原理（通俗易懂版）
• 深度优先搜索-维基百科

文章最后发布于: 2018-03-27 19:21:46

相关阅读

王子救公主 （计蒜客）一道简单DFS

蓝桥杯不能粘贴  只能截图。。 这道题目很简单，主要想清楚 只要存在王子和公主都能到达的点，王子就能救出公主（此时必定有一个时刻

C - Fliptile （黑白棋翻转经典题型 DFS）

C - Fliptile Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arr

SPFA 算法详解( 强大图解，不会都难！)&&spfa优化——深度

https://blog.csdn.net/muxidreamtohit/article/details/7894298　　适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了

FastDFS使用流程

一、什么是FastDFS?    FastDFS 是用 C 语言编写的一款开源的分布式文件系统，对文件进行管理，主要功能包括：文件存储、文件同步、

FastDFS文件服务器——安装教程及命令，亲测使用

搭建单机模式的Fastdfs文件服务器链接（成功搭建）http://blog.csdn.net/u010098331/article/details/51646921参考的博客FastDFS分布