C语言递归+DFS(深度优先搜索算法)详解 图文并茂,手把手教你画树状图 |
您所在的位置:网站首页 › 深度优先搜索算法详解 › C语言递归+DFS(深度优先搜索算法)详解 图文并茂,手把手教你画树状图 |
目录 一.标准定义 二.跳台阶(典型递归题目) 三.递归实现指数型枚举 四.递归实现排列型枚举 五.递归实现组合型枚举 六.DFS算法模板 一.标准定义 深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
说人话,其实就是沿着一条路一直搜索,知道条件不符合,就回头走到分岔口,选择另一条路继续搜索,俗称:“不撞南墙不回头”搜索。 这种一直进行下去又返回的操作是不是很像递归,dfs名字听起来高大上,其实本质就是递归。那我们就先从一道典型的递归题开始说起吧。 二.跳台阶(典型递归题目)上楼梯的同学,每次可以走一个台阶,也可以走两个台阶,现在有N个台阶,请问有多少种不同的方法?(先爬1阶再爬2阶和先爬2阶再爬1阶是不同的方法) 我们可以自己在草稿纸上算算,看看有什么规律。 N=1,1种; N=2,1+1/2 2种 N=3 1+1+1/1+2/2+1 3种 N=4 1+1+1+1/2+2/1+2+1/2+1+1/1+1+2 5种 ...... 很显然,其实你会发现答案成斐波那契数列(当然,本题答案是从斐波拉契数列第二项开始的)。这就把题目转换成我们熟悉的问题了。 对于斐波那契数列,我们可以引用一种”递归搜索树“的方法,来让整个过程更加直观。 2024.3.17更新 今天发现之前传的图有错误,重新画了一张,同时给大家做了一个搜索视频,方便大家理解,更直观的展现了dfs搜索的过程。特别是回溯,感受一下这个回溯的过程。
我们先沿着左边①这条路一直往下算,直到遇到了f(2)(因为我们知道f(1),f(2)的值),然后撞到了”南墙“,我们就开始回溯,算f(1),两者累加算出f(3)的值,接着回溯算f(2)的值...... 这个过程其实就体现了什么加”深度搜索“,什么叫”回溯“。 我们简单看一下这道题的代码。 #include int fun1(int n) { if (n == 1) return 1; else if (n == 2) return 2; else return fun1(n - 1) + fun1(n - 2); }什么?觉得简单?我们开始上强度了。 再讲下面题之前,我先给出dfs算法基本套路。 三.DFS算法模板 1.创建一个数组,存储状态和结果。 2.函数内部 ①判断是否撞了南墙 ②执行赋值,改状态的操作 ③再次调用函数 ④恢复现场 四.递归实现指数型枚举我们先看看这道题。可以尝试运用树形图的方法找找思路。 通过判断一个数选不选的思路,我们可以画出树状图。 这是我没画完的树状图,你看,这样就能找到2个答案了。 我们把图补全,8个答案就已经全部找到了。 接着,我们进行代码实现,注意看我的注释> 如何让程序知道一个数选没选呢?那就需要使用一个状态数组,存储一个数的状态,是选了还是没选还是还没考虑到。 #include int n; int st[20] = { 0 };//记录每个数的状态,0代表还没考虑,1代表选了,2代表没选 void dfs(int x)//x表示当前枚举到了哪个位置 { //判断是不是撞了"南墙"了 if (x > n) { for (int i = 1; i不要慌张,熟能生巧~ 五.递归实现排列型枚举同样的,上例题 当n=3时,由高中学的排列组合知识,那么就有A3 3=3*2*1=6种排列方式,符合输出结果。 我们可以根据依次枚举一个位置上选哪个数的思路,来画个树状图,试试呢? 我们一起来看看代码如何实现的 #include #include int n = 0; bool st[10];//因为一个数只能出现一次,所以用一个状态数组存一下一个数是否已经被选。 //true表示选过,false表示未被选。 int arr[10] = { 0 };//存的是答案,例如123/321/312 //x表示枚举到的位置 void dfs(int x) { if (x>n) { for (int i = 1; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |