文章参考：https://blog.****.net/chensanwa/article/details/79717835

DFS学习总结

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

深度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问。沿着某条路径遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。

主题思想：不南墙不回头

简述算法过程

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

DFS其实就是找准一条路径（我们可以暂且这样认为），一直走下去（深度优先），直到满足条件（这属于运气好了）或者走投无路、走不下去（撞南墙了）。如果没有找到相应的结果状态，那么就回退一步（回溯），再进行下一步找路径，再撞再回溯，一直到找到目标状态或者所有情况都遍历完，程序结束。

图解：

DFS总结

//图片来自：https://blog.****.net/chensanwa/article/details/79717835

This is the codes

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EPS 1e-8
#define MOD 1e9+7
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x7f7f7f7f      //2139062143
#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
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;
}

DFS总结

文章参考：https://blog.****.net/chensanwa/article/details/79717835

DFS学习总结

主题思想：不南墙不回头

相关推荐