优先深度优先搜索广度优先搜索或反之亦然

我研究了两种图遍历算法，深度优先搜索和广度优先搜索。由于两种算法都用于解决图遍历的相同问题，所以我想知道如何在两者之间进行选择。我的意思是比另一个更有效率，或者说为什么我会在特定场景中选择另一个。优先深度优先搜索广度优先搜索或反之亦然

谢谢你

2012-05-15 Kris

请参阅http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first ...包含一些有用的信息和链接，包括链接到最后两个答案之一的3部分博客。 – hatchet

感谢分享this.It看起来真的很有用。实际上，我明白这两种算法如何工作，只是想知道为什么我们需要其中两个:) – Kris

类似于http://stackoverflow.com/questions/1657174/what-对于 – hatchet

与我的主要区别是有些理论上的。如果你有一个无限大小的图，那么如果它存在于它选择的第一个路径之外，DFS将永远不会找到一个元素。它基本上会继续沿着第一条路走下去，永远不会找到这个元素。 BFS最终会找到这个元素。

如果图的大小是有限的，那么DFS可能会更快地发现异常值（根与目标之间的距离更大），因为BFS会更快地找到更近的元素。除了DFS选择浅层元素的路径。

来源

2012-05-15 17:50:37 Justin

这不是一个错误的答案，但是DFS和BFS都可以在无限的情况下失败 - 如果图形无限深，DFS可能会失败，而BFS可以工作。但是，如果图形不是无限深的，而是无限*广泛*，则DFS将起作用，而BFS将失败。遍历无限图（根据我的理解）与遍历有限图大不相同。 –

一般来说，BFS对于找到最短路径或相关问题相关的问题更好。因为在这里你从一个节点到所有与它相邻的节点，因此你有效地从路径长度移动到路径长度二，等等。

虽然另一端的DFS更有助于解决连接问题，并且还可以查找图表中的循环（尽管我认为您也许可以通过修改BFS来查找循环）。确定与DFS的连接性是微不足道的，如果您从DFS过程中调用两次浏览过程，那么图形将断开连接（这是针对无向图的）。这里可以看到有向图的强连通分量算法，这是对DFS的修改。 DFS的另一个应用是拓扑排序。

这些都是算法的一些应用：

DFS：

连接
强连通分量
拓扑排序

BFS：

最短路径（Dijkstra算法是一些什么的BFS修改）。
测试图形是否为二分图。

来源

2012-05-15 18:14:33 sukunrt

对于完整/完美的树，DFS相对于树的深度需要线性空间量，而BFS相对于树的深度需要指数量的空间。这是因为对于BFS，队列中的最大节点数与树的一个级别中的节点数成比例。在DFS中，堆栈中的最大节点数量与树的深度成比例。

来源

2015-01-01 00:28:41

当遍历多连接图时，遍历节点的顺序可能会对遍历方法要跟踪的节点数量产生很大影响（以多个数量级）。某些种类的算法在使用宽度优先时会大大提高;其他人在使用深度搜索时会大大改善。

一方面，对具有N个叶节点的二叉树进行深度优先搜索要求遍历方法跟踪lgN节点，而广度优先搜索需要跟踪至少N/2个节点（因为它在扫描任何叶节点之前可能会扫描所有其他节点;在扫描第一个叶节点之前，它将遇到叶节点的父节点的N/2个，这些节点必须单独进行跟踪，因为它们都没有相互引用）。另一个极端是，用一种方法在NxN网格上进行填充，如果其像素尚未着色，则对该像素进行着色，然后对其邻居进行洪水填充将需要排入O（N）如果使用宽度优先搜索，则使用像素坐标;如果使用深度优先，则使用O（N^2）像素坐标。在使用广度优先搜索时，无论要绘制的形状如何，绘画都会“展开”当使用深度优先算法绘制矩形螺旋时，每条直线的一侧是直的而另一侧是交错的（哪一侧应该是直的并且锯齿取决于所使用的确切算法），所有的直线部分将被绘制在任何锯齿状之前，意味着系统必须分别跟踪每个锯齿的位置。

来源

2015-04-30 17:01:20 supercat

在某些语言中，BFS是一个稍微更好的选择因为最简单的实现DFS的是递归的，它引入了额外的开销，而且也可能会导致您的代码打堆栈大小限制大图。 BFS的明显优势（和应用）是，在未加权图中它可以用来构造从u到v的最短路径。这有很多应用程序 - 例如，您可以计算最少的移动次数需要通过在其状态空间上运行BFS来解决给定的难题。 BFS甚至可以为您提供一个顶点u到图中所有其他顶点的最短距离：对于每个顶点，只需记住用于发现它的边缘。

来源

2015-10-28 02:53:12

优先深度优先搜索广度优先搜索或反之亦然

回答

相关问题