首页 > 其他分享 >【代码随想录】深度优先搜索

【代码随想录】深度优先搜索

时间:2024-03-20 12:00:15浏览次数:18  
标签:优先 模版 随想录 dfs 搜索 回溯

首先了解一下深度优先搜索和回溯法的区别
image
可以看出这两种方法在思路上可以说没什么区别,但是由于在具体实现方面的区别,有着不同的应用场景。
我的理解是,回溯法很多时候是应用在抽象的枚举过程中的,而dfs算法很多时候是用在图或者树这种实际的几何图形中的。
比较一下回溯的模版和dfs的模版:
image

image

dfs思路分析三步骤:

1.确定dfs函数和参数
image
(其实就相当于回溯法里的全局变量path和res)
2.确定递归终止函数
image
3.dfs函数内的操作
image
(不用多说,和回溯的分析一样)

总结

dfs可以说在各种地方都和回溯的思路一样,只不过应用场景不同造成实现的细节上有差别。

标签:优先,模版,随想录,dfs,搜索,回溯
From: https://www.cnblogs.com/satsuki26681534/p/18084245

相关文章