文章目录
宽度优先搜索深度优先搜索BFS vs DFS什么是二叉树的BFS和DFS？在额外空间方面有什么区别吗？如何选择？参考文档
宽度优先搜索
BFS代表Breadth First Search，是一种基于顶点的技术，用于在图中查找最短路径。它使用先进先出的队列数据结构。在BFS中，一次选中并标记一个顶点，然后其相邻顶点被访问并存储在队列中。它比DFS慢。
A
/ \
B C
/ / \
D E F
输出为：
A, B, C, D, E, F
深度优先搜索
DFS代表Depth First Search，是一种基于边的技术。它使用栈数据结构，执行两个阶段，首先将已访问的顶点推入堆栈，然后如果没有未被访问的顶点，则弹出已访问的顶点。
A
/ \
B C
/ / \
D E F
输出为：
A, B, D, C, E, F
BFS vs DFS
序号BFSDFS1BFS代表宽度优先搜索DFS代表深度优先搜索2BFS（宽度优先搜索）使用队列数据结构来查找最短路径DFS（深度优先搜索）使用栈数据结构3BFS更适合搜索更接近给定源的顶点如果有远离源的解决方案，则DFS更适合4BFS首先考虑所有邻居，因此不适合用于游戏或拼图中的决策树。DFS更适用于游戏或拼图问题。我们做出决定，然后探索有关该决定的所有路径。如果这一决定带来获胜局面，我们将停止。5当使用邻接表时，BFS的时间复杂度为O（V+E）；当使用邻接矩阵时，BFS的时间复杂度为O（V^2），其中V表示顶点，E表示边。当使用邻接表时，DFS的时间复杂度也是O（V+E），当使用邻接矩阵时，DFS的时间复杂度也是O（V^2），其中V表示顶点，E表示边。
什么是二叉树的BFS和DFS？
通常以两种方式遍历一棵树：
宽度优先遍历深度优先遍历
中序遍历（左 - 根 - 右）前序遍历（根 - 左 - 右）后序遍历（左 - 右 - 根）
BFS and DFSs of above Tree
Breadth First Traversal : 1 2 3 4 5
Depth First Traversals:
Preorder Traversal : 1 2 4 5 3
Inorder Traversal : 4 2 5 1 3
Postorder Traversal : 4 5 2 3 1
在额外空间方面有什么区别吗？
所需的额外空间有所不同。
水平顺序遍历所需的额外空间为O（w），其中w是二叉树的最大宽度。在水平顺序遍历中，一个接一个的队列存储不同级别的节点。深度优先遍历所需的额外空间是O（h），其中h是二叉树的最大深度。在深度优先遍历中，栈（或函数调用栈）存储节点的所有祖先。
深度（或高度）h处二叉树的最大宽度可以是
2
h
2^h
2h，其中h从0开始。所以节点的最大数目可以在最后一级。最坏的情况发生在二叉树是一个节点数为1，3，7，15…的完美二叉树。最坏情况下，
2
h
2^h
2h的值为Ceil（n/2）。 平衡二叉树的高度为O（Log n）。最坏的情况发生在倾斜的树上，最坏的情况是高度变为O（n）。 因此，在最坏的情况下，两者所需的额外空间均为O（n）。但是最坏的情况发生在不同类型的树上。 从以上几点可以明显看出，当树更平衡时，水平顺序遍历所需的额外空间可能更多，而当树不太平衡时，深度优先遍历所需的额外空间可能更多。
如何选择？
额外空间可能是一个需要考虑的因素（上面已解释）深度优先遍历通常是递归的，递归代码需要函数调用系统开销。最重要的一点是，BFS从根开始访问节点，而DFS从叶开始访问节点。所以，如果我们的问题是搜索更接近根的东西，我们更喜欢BFS。如果目标节点靠近叶子，我们会选择DFS。
参考文档
[1]MKS075.Difference between BFS and DFS[EB/OL].https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/,2020-07-03. [2]Dheeraj Gupta.BFS vs DFS for Binary Tree[EB/OL].https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/,2016-12-22.