图论--DFS总结
2024-08-31 08:55:49
1.Key word:①双向DFS ②回溯
今天就看到了这么多DFS,其实DFS更倾向于枚举所有情况。
对于双向DFS,我们考虑看看最短路,起点做一下搜索,记录一下到所有点的距离,终点做一下搜索,记录一下到所有点的距离,那么起点到任一点的距离加上终点到任一点的距离那不就是起点到终点经过这一点的最短距离,我觉得BFS也可以实现,所以在我眼里BFS相对于DFS更强一点,只有说得到特定的某一结果的时候深搜可能会好一点。
设计回溯,所谓回溯就是还原现场,保证在执行另一分支的时候能够保证所以的改变只受当前状态的影响,所以在一条路走不通时就要修改,不过通过特殊的修改可以达到特殊的回溯效果,回溯时剪枝,回溯时调整路线,都是可以的。
DFS题型: 哈密尔顿路径 欧拉回路 连通性 枚举题目 全排列(也是枚举)所以DFS对于状态的找寻比较局限,目前还没看到更好的题目。
后期还会继续更新,与填坑。
关于BFS详细总结戳这里:https://blog.csdn.net/weixin_43627118/article/details/100088087
最新文章
- iOS开发:读取pdf文件
- 通过实验窥探javascript的解析执行顺序
- Lucene实战构建索引
- web iphone css 兼容性
- percona-toolkit工具包的使用教程之开发类工具
- python练习程序(c100经典例4)
- adb shell 出现 error :
- oracle11g 创建用户并授权
- Android开发中内置apk程序
- Linux - VIM(VI)编辑器
- Octave Tutorial(《Machine Learning》)之第四课《绘图数据》
- Javascript-数值运算 保留小数点位数,并对最后一位小数各种取整方法
- [ExtJS5学习笔记]第十四节 Extjs5中data数据源store和datapanel学习
- 微机原理基础(四)—— MSC51
- me
- es6中promise ALL Race Resolve Reject finish的实现
- makefile 里的 := , = , +=
- JS中循环逻辑和判断逻辑的使用实例
- JdbcTemplate 方法使用
- python获取当前日期