面试算法大全-深度优先遍历和广度优先遍历

本文主要是介绍面试算法大全-深度优先遍历和广度优先遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

13.1 深度优先遍历和广度优先遍历算法总结

​ 广度优先搜索算法（Breadth-First-Search，缩写为 BFS），是一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

​ 深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。简单来说，其搜索过程和 “不撞南墙不回头” 类似。

​ BFS 的重点在于队列，而 DFS 的重点在于递归。这是它们的本质区别。

​ DFS 和 BFS 都是常用来遍历搜索树或图的算法。二叉树中的前序、中序和后序遍历都属于DFS，层次遍历属于BFS。DFS常用递归和栈来实现，BFS常用队列来实现。

• BFS用queue (程序中用的deque，不用deque直接用普通队列一样的)

• • 按BFS的方法遍历整个树，即用队列先后保存左右子节点，这样就可以一层一层的记录每个节点的val，输出到res中

  • 利用了queue先进先出的特点，append时先左再右，这样pop时的顺序也是先左再右

    

这篇关于面试算法大全-深度优先遍历和广度优先遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！