算法很美之深度优先搜索(DFS)

用户102

2023年10月29日修改

⏳

Written 03-29-2021

写在前面

算法很美,真的很美

当我们去尝试理解某种算法的过程中可能不会那么顺利

一旦悟透了其中的思想,不仅能让我们身心愉悦,更能丰富编程思维​

从这篇博客开始我准备写一系列关于算法的博客,顺便备赛一下蓝桥杯​

基本概念

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件(不满足条件也被称为剪枝)，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。​

算法思想

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 ​

我这里准备了一张GIF图片,希望能够帮助你理解其中的思想

common.docs_name - LarkCCM_Docs_Menu_Image

💡

DFS可以理解为一条路走到底,不撞南墙不回头

撞南墙有两种情况

•
 遇到了边界条件(限制条件)​

•
 遇到了已经走过的路​

DFS的另一种结束条件,就是找到了目标出口,也就是找到了题目的答案​

💡

DFS的本质其实就是枚举

算法模板

光看概念就想理解一种算法肯定不太现实,所以接下来我会通过两道题目进行讲解​

在做题之前,我们可以看看这种题目的算法模板

看不懂没关系,当你做完后面的两道题目的时候

再回过头来看,我相信你一定能够茅塞顿开

代码块

-----------------------深度优先搜索-----------------------​
def dfs(current: int):​
    if (判断边界):​
        输出结果​
​
    for (尝试每一种可能):​
        if (满足check条件):​
            标记​
            继续下一步dfs(current + 1)​
            回溯, 恢复初始状态(可根据题目要求选择是否回溯)​
​
def check(param):​
    if (满足条件):​
        return Ture​
    return False​
-----------------------深度优先搜索-----------------------​

算法很美之深度优先搜索(DFS)​

算法很美之深度优先搜索(DFS)