『算法-ACM 竞赛-图论』DFS 总结

图论–DFS 总结

1.Key word：① 双向 DFS ② 回溯

今天就看到了这么多 DFS，其实 DFS 更倾向于枚举所有情况。

对于双向 DFS，我们考虑看看最短路，起点做一下搜索，记录一下到所有点的距离，终点做一下搜索，记录一下到所有点的距离，那么起点到任一点的距离加上终点到任一点的距离那不就是起点到终点经过这一点的最短距离，我觉得 BFS 也可以实现，所以在我眼里 BFS 相对于 DFS 更强一点，只有说得到特定的某一结果的时候深搜可能会好一点。

设计回溯，所谓回溯就是还原现场，保证在执行另一分支的时候能够保证所以的改变只受当前状态的影响，所以在一条路走不通时就要修改，不过通过特殊的修改可以达到特殊的回溯效果，回溯时剪枝，回溯时调整路线，都是可以的。

DFS 题型： 哈密尔顿路径 欧拉回路 连通性 枚举题目 全排列（也是枚举）所以 DFS 对于状态的找寻比较局限，目前还没看到更好的题目。

后期还会继续更新，与填坑。

关于 BFS 详细总结戳这里：https://blog.csdn.net/weixin_43627118/article/details/100088087