图论--DFS总结

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

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

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

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

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

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

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