【总结】DFS 模板套路及例题详解

小咪咪 2023-07-02 12:23 12阅读 0赞

###  ###

*  深度优先搜索
 *  DFS 模板套路
 *  DFS 经典题目

> 以下内容收集了全网以及整合了自己写的部分。

# 深度优先搜索 #

*  深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。
 *  沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。
 *  整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
 *  思想：一直往深处走，直到找到解或者走不下去后回溯。
 *  **DFS和BFS的区别：** 深搜和广搜在实现上分别用的是栈（栈和函数递归本质是一样）和队列。一般来说，广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解"， 而深搜用于找多个解或者是"步数已知（好比3步就必需达到前提）"的标题，它的空间效率高，然则找到的不必定是最优解，必需记实并完成全数搜索，故一般情况下，深搜需要很是高效的剪枝（优化）.

# DFS 模板套路 #

**简单版**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]

**详细版**

//模板1
    #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;
    }
    
    
    //模板2
    void dfs()//参数用来表示状态 
    {   
        if(到达终点状态){   
            ...//根据题意添加 
            return;  
        }  
        if(越界或者是不合法状态)  
            return;  
        if(特殊状态)//剪枝
            return ;
        for(扩展方式){   
            if(扩展方式所达到状态合法){   
                修改操作;//根据题意来添加 
                标记；  
                dfs（）；  
                (还原标记)；  
                //是否还原标记根据题意 
                //如果加上（还原标记）就是 回溯法 
            }  
     
        }  
    }

# DFS 经典题目 #

*  [【洛谷】P1605 迷宫][P1605]
 *  [【洛谷】P1219 八皇后][P1219]
 *  [【洛谷】P1101 单词方阵][P1101]
 *  [【HDU】2563 统计问题][HDU_2563]
 *  [【HDU】1035 Robot Motion ][HDU_1035 Robot Motion]
 *  [【HDU】1045 Fire Net ][HDU_1045 Fire Net]
 *  [【HDU】1010 Tempter of the Bone (奇偶剪枝优化)][HDU_1010 Tempter of the Bone]
 *  [【HDU】1016 Prime Ring Problem ][HDU_1016 Prime Ring Problem]
 *  [【HDU】1015 Safecraker ][HDU_1015 Safecraker]
 *  [【HDU】1258-Sum It Up (去重技巧)][HDU_1258-Sum It Up]
 *  [【HDU】2676 Sudoku (数独问题)][HDU_2676 Sudoku]

> **题解：** [DFS 经典题目详解][DFS]

还不够熟练？那就再训练以下题目

[【kuangbin 带你飞】专题一 简单搜索 题解][kuangbin _ _]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129225006744.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70
[P1605]: https://www.luogu.com.cn/problem/P1605
[P1219]: https://www.luogu.com.cn/problem/P1219
[P1101]: https://www.luogu.com.cn/problem/P1101
[HDU_2563]: http://acm.hdu.edu.cn/showproblem.php?pid=2563
[HDU_1035 Robot Motion]: http://acm.hdu.edu.cn/showproblem.php?pid=1035
[HDU_1045 Fire Net]: http://acm.hdu.edu.cn/showproblem.php?pid=1045
[HDU_1010 Tempter of the Bone]: http://acm.hdu.edu.cn/showproblem.php?pid=1010
[HDU_1016 Prime Ring Problem]: http://acm.hdu.edu.cn/showproblem.php?pid=1016
[HDU_1015 Safecraker]: http://acm.hdu.edu.cn/showproblem.php?pid=1015
[HDU_1258-Sum It Up]: http://acm.hdu.edu.cn/showproblem.php?pid=1258
[HDU_2676 Sudoku]: http://poj.org/problem?id=2676
[DFS]: https://blog.csdn.net/weixin_44668898/article/details/104115884
[kuangbin _ _]: https://blog.csdn.net/weixin_44668898/article/details/102790967