Braincao's Blog

这是一篇关于DFS深度优先搜索算法的总结笔记

DFS思想

参考：BFS和DFS算法原理（通俗易懂版）

DFS模板

#include <iostream>
using namespace std;

/**
 *DFS思想：一直往深处走，直到找到解或者走不下去为止
 *实现：采用递归，使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
 *该DFS框架以2D坐标范围为例，来体现DFS算法的实现思想。
*/

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)周围的四个方向：dir[0]上，dir[1]下，dir[2]右，dir[3]左

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] == 1) // 出现目标态G
    {
         // 做相应处理
        return;
    }
    for(int i=0;i<4;i++) //遍历(x, y)上下左右四个方向进行搜索
    {
        if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
            dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; // 没有下层搜索节点，回溯
}
int main()
{

    return 0;
}

---

欢迎转载，欢迎错误指正与技术交流，欢迎交友谈心