经典算法题之（知识补充）------ BFS和DFS的感性认识

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了经典算法题之（知识补充）------ BFS和DFS的感性认识，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2404字，纯文字阅读大概需要4分钟。

内容图文

在经典算法题之（六）------ 二维数组迷宫问题中列举了很多种情况，从条件放宽到可以任意走开始，就成了图的最短路径问题，一旦涉及到图的最短路径，则一定会用到DFS和BFS（能手写Dijkstra的话当我没说。。）。而这种两种思想在解决图的问题时也特别普遍，实际上，在二叉树的很多问题中也同样要用到这两种方法，特别是DFS，因为二叉树的三中遍历方法从本质上来说就是DFS，只是访问节点的位置（在递归之前还是中间还是之后）不同。

所以，为了形象地认识DFS和BFS，特地做了两个GIF。

深度优先搜索DFS：

 

广度优先搜索BFS：

PS：引用这两个GIF请加上引用说明！！！花了很大的功夫才做好 w.w

其实一目了然，左上角是起点，右下角是终点，白色为障碍物，黄色为可以走但还没有走的位置，蓝色为正在走的位置，灰蓝色为已经走的位置。

可以看到：

① 形象地去看，BFS像是浪花一圈圈向外扩散（那么障碍物就是鹅卵石），或者像是瘟疫传染，下次访问的必然是本次访问节点能够传染的其他节点（够得着），在代码实现中，本次访问的就是当前队列中的节点，下次访问（传染）的就是以当前节点作为传染源的其他节点。

可以想见，如果现在在图的中央放置一个“传染源”，那么BFS的遍历结果就像是在湖中心投了一颗石子，一直扩散到四周的岸边（当然，达到可能到岸的时间不一样）。

② 而DFS，更像是挖矿，一根筋地往“深处”挖，认准一个方向，只要这个方向还挖的下去，就一直挖，如果这个方向挖不下去了，则在当前节点处换个方向挖，如果几个方向都挖过了，则回退。

一般来说，DFS在当前层递归时至少调用两次方法（因为至少是二叉树才用得到DFS），在上述可以自由走动的图时，一般要调用四次方法（四个方向），或者在更一般的图中，要遍历当前节点的所有“邻居”节点。用挖矿的角度看，这个遍历的顺序并不影响，如上图中，对于当前节点，可以顺时针“探测”，也可以“逆时针”探测，此时调用次序的定义更像是如何设计“探针”——无论怎么设计，只会影响访问的次序，并不会影响访问的最终结果——所有节点都访问且只访问了一次。

 

综合BFS和DFS来看，BFS和DFS都达到了访问联通图中所有节点的效果，但BFS没有使用递归栈，没有回溯的过程（一路向前），故效率更高。

关于效果为什么没有差别，可以先局部再整体的方法分析。

局部来看，对于每个节点来说，访问本节点必然只能由本节点的邻居节点而来，也就是说，如果我遍历所有的邻居访问你的可能，并且取最小的，那么这个最小值就是访问到你的最短路径。

整体来看，BFS和DFS都访问且只访问了所有节点一次，即对于任意一个节点，BFS和DFS必然都访问了你的所有邻居，并且在访问你的邻居时更新了到你的最短路径，具体到代码实现上，就是访问当前节点时，更新到其邻居的dp值，对于DFS来说，更新其邻居dp值和进行下层递归放在一起了：每个节点使用探针进行探测时，第一遍的操作是更新其最短路径，然后才是判断是否为障碍物，是否已经访问过了，如果没有，则访问。

内容总结

以上是互联网集市为您收集整理的经典算法题之（知识补充）------ BFS和DFS的感性认识全部内容，希望文章能够帮你解决经典算法题之（知识补充）------ BFS和DFS的感性认识所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---