深度优先搜索和广度优先搜索各自的优势是什么？

Question

我已经学习了两种图遍历算法：深度优先搜索和广度优先搜索。由于这两种算法都用于解决图遍历问题，因此我想知道如何在它们之间进行选择。我的意思是，在特定情况下，是否有一种算法比另一种更有效，或者选择其中一种的任何原因？

谢谢。

- Kris

---

请看 https://dev59.com/oHRB5IYBdhLWcg3wNk93，其中包含一些有用的信息和链接，包括最后两个答案中链接到的三部分博客。 - hatchet - done with SOverflow

谢谢分享。看起来非常有帮助。实际上，我确实理解这两个算法的工作原理，只是想知道为什么我们需要两种算法 :) - Kris

请问广度优先搜索有什么用途？ - hatchet - done with SOverflow

可能是图形数据结构：DFS vs BFS？的重复问题。 - Ciro Santilli OurBigBook.com

Answer 1

对我而言，主要区别在于一定程度上是理论性的。如果有一个无限大小的图，那么深度优先搜索（DFS）将永远不会找到某个元素，如果该元素存在于它选择的第一条路径之外。它基本上会沿着第一条路径继续下去，永远也找不到该元素。广度优先搜索（BFS）最终会找到该元素。

如果图的大小是有限的，则 DFS 很可能会更快地找到一个离群值(根节点和目标节点之间距离较大的节点) ，而 BFS 会更快地找到更接近目标节点的元素。除非 DFS 选择了浅元素的路径。

- Justin

---

这并不是一个糟糕的答案，但深度优先搜索和广度优先搜索在无限情况下都可能失败——当一个图是无限深时，深度优先搜索可能会失败，而广度优先搜索则可能成功。然而，如果图不是无限深而是无限宽，那么深度优先搜索将会成功，而广度优先搜索则会失败。从我的理解来看，遍历无限图与遍历有限图大不相同。 - user677526

Answer 2

一般来说，BFS 更适用于寻找最短路径或相关问题。因为你从一个节点到其所有相邻的节点，因此你有效地从路径长度 1 移动到路径长度 2 等等。

而 DFS 则更有助于解决连接问题以及在图中寻找循环(虽然我认为你也可以通过对 BFS 的轻微修改找到循环)。使用 DFS 确定连通性是微不足道的。如果您从 DFS 过程中调用两次 explore 过程，则图形是断开的(这是针对无向图的)。您可以在此处查看有向图的强连通分量算法，该算法是 DFS 的一种修改。DFS 的另一个应用是拓扑排序。

这些是两种算法的一些应用:

DFS:

- 连通性 - 强连通分量 - 拓扑排序

BFS:

- 最短路径(Dijkstra 稍微修改了 BFS) - 测试图是否为二部图。

- sukunrt

Answer 3

在遍历一个多重连通图时，节点的遍历顺序可能会极大地影响（数个数量级）遍历方法需要跟踪的节点数。一些算法在使用广度优先搜索时将会显着优于深度优先搜索，而其他算法则完全相反。

在极端情况下，对具有N个叶节点的二叉树进行深度优先搜索需要让遍历方法跟踪lgN个节点，而广度优先搜索则需要至少跟踪N/2个节点（因为它可能会在扫描任何叶节点之前扫描所有其他节点；在扫描第一个叶节点之前，它将遇到N/2个叶节点的父节点，这些节点必须单独跟踪，因为它们之间没有引用关系）。

在另一个极端，使用一种方法在NxN网格上进行泛洪填充，如果其像素尚未着色，则会对该像素进行着色，然后填充其邻居，如果使用广度优先搜索，则需要将O(N)个像素坐标加入队列，但如果使用深度优先搜索，则需要将O(N^2)个像素坐标加入队列。当使用广度优先搜索时，绘画似乎会“扩散”，无论要绘制的形状如何；当使用深度优先算法绘制一个矩形螺旋线时，其中每条线的一侧是直的，另一侧是锯齿状的（哪些侧应该是直的和锯齿状的取决于所使用的确切算法），所有直线部分都将被涂上颜色，然后才会涂上任何锯齿状的部分，这意味着系统必须单独跟踪每个锯齿状部分的位置。

- supercat

Answer 4

对于完全/理想的树而言，深度优先搜索算法所需的空间与树的深度成线性关系，而广度优先搜索算法则与树的深度呈指数关系。这是因为在广度优先搜索中，队列中最多存储节点数量与树某一层的节点数成比例；而在深度优先搜索中，栈中最多存储节点数量与树的深度成比例。

- Kevin Wheeler