嗨,你好。 这里是馅饼大鑫,不是冷咖啡。 基于基础不牢、地动山摇的学习态度,从基础的c语言语法到算法,再到更高级的语法和框架的学习。 同样的编程(或对应期末考试的狗耳朵. jpg ) )让大家在学习阶段能找到好的方法、课程,天下没有难的程序)只有秃顶的程序设计者2333 )、程序和啊
本文详细介绍了经典算法DFS从何而来,为什么要在几个方面进行阐述,深度优先搜索并不是一次完成,而是内容互补,存在不足之处,受到了广大读者的包容
1. 深度优先搜索介绍图的深度优先搜索(Depth First Search )与树的初始遍历相比类似。
这是指,假设初始状态为图中的所有顶点未被访问,则从某个顶点v出发,首先访问该顶点,然后在图中的v和通过路径的所有顶点被访问之前,从各未被访问的邻接点开始依次优先搜索扫描图如果尚未访问该时尚的其他顶点,请选择另一个未访问的顶点作为起点,然后重复上述步骤直到访问图中的所有顶点。
很明显,深度优先搜索是一个递归过程。
以有向图为例
假设按字母顺序遍历所有顶点,即V=[a,b,c,d,e,f],则原图为
在最初的步骤中探索从a到b的边,发现b还有边,向下进行到d,d没有边向下进行,最初的DFS-Visit执行结束
开始回溯,首先追溯到d的父节点e。 同样,到a为止,a的另一边是a到d,但d已经被探索过了,不进行操作
改变源点执行搜索。 这个时候是b,但b已经在探索了。 进一步搜索c,可以发现只有与一边对应的f没有进行搜索
即使在f之前继续交换源点,也没有新的未探索的边
2 .深度优先探索的一般形式
在以前的列举中需要固定for循环的段数,但是程序非常冗长,不能自由增减列举段数。
因此我们采用了更高效的算法——DFS
通过递归枚举函数,枚举每个“空”的所有可能选择,并确定该选择是否合法。 如果此选项合法,请填写以下选项并继续;
如果此空栏中的所有选项都不合法(或遍历结束),请尝试替换上一个空栏中的选项并继续枚举,而不是继续枚举。
这种方式称为回溯算法,多采用深度优先搜索来实现。
大家最关心的是如何实现深度优先搜索算法吧。 这里列出了最常见的模板。
voidDFS(intk ) )/k表示递归层数,或者填入几个空的if (所有的空都填好了)判断最优解/记录答案; 返回; (for )列举此空白被填充的选项) if )记录此空白(保存现场) DFS ) k1 ); //选择下一个空,取消这个空((修复现场) ) ) )之后恢复空以填补) )在这里留下一些疑问,在空闲的时候慢慢补充) ((0)
)1)什么时候需要取下标志?
)2)什么时候用DFS算法解题
)3) DFS典型例题解答
)4) DFS和BFS的区别(这里重新写文章进行说明)。
……之后有什么想法就补充一下吧(准备考研,真的很忙,但是我先尊敬鸽子! )