我了解 DFS 和 BFS 之间的区别，但我很想知道何时使用其中一种更实用？
谁能举例说明 DFS 如何胜过 BFS，反之亦然？
问问题
315299 次
15 回答
440
这在很大程度上取决于搜索树的结构以及解决方案的数量和位置（也称为搜索项）。
如果您知道解决方案离树的根不远，那么广度优先搜索 (BFS) 可能会更好。
如果树非常深且解决方案很少，则深度优先搜索 (DFS) 可能需要极长的时间，但 BFS 可能会更快。
如果树非常宽，BFS 可能需要太多内存，因此它可能完全不切实际。
如果解决方案频繁但位于树的深处，则 BFS 可能不切实际。
如果搜索树非常深，则无论如何都需要限制深度优先搜索 (DFS) 的搜索深度（例如使用迭代加深）。
但这些只是经验法则；您可能需要进行实验。
我认为在实践中你通常不会以纯粹的形式使用这些算法。可能有启发式方法可以帮助首先探索搜索空间的有希望的部分，或者您可能希望修改搜索算法以便能够有效地并行化它。
于 2010-07-26T07:32:46.993 回答
208
深度优先搜索
深度优先搜索通常用于模拟游戏（以及现实世界中的类似游戏的情况）。在典型的游戏中，您可以选择几个可能的动作之一。每个选择都会导致进一步的选择，每个选择都会导致进一步的选择，依此类推，形成一个不断扩大的树形可能性图。
例如，在国际象棋、井字游戏等游戏中，当您决定采取什么行动时，您可以在脑海中想象一个行动，然后是对手可能的反应，然后是您的反应，等等。您可以通过查看哪个动作会带来最佳结果来决定要做什么。
只有游戏树中的某些路径会导致您获胜。有些会导致你的对手获胜，当你达到这样的结局时，你必须备份或回溯到前一个节点并尝试不同的路径。通过这种方式，您可以探索树，直到找到一条成功结束的路径。然后你沿着这条路迈出第一步。
广度优先搜索
广度优先搜索有一个有趣的特性：它首先找到距离起点一条边的所有顶点，然后找到距离起点两条边的所有顶点，以此类推。如果您试图找到从起始顶点到给定顶点的最短路径，这很有用。你启动一个 BFS，当你找到指定的顶点时，你就知道到目前为止你所追踪的路径是到节点的最短路径。如果有更短的路径，BFS 早就找到了。
广度优先搜索可用于查找对等网络（如 BitTorrent）中的邻居节点、GPS 系统查找附近位置、社交网站查找指定距离内的人等等。
于 2016-05-06T09:35:06.197 回答
127
来自http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/的很好的解释
BFS 的一个例子
这是 BFS 的外观示例。这类似于 Level Order Tree Traversal，我们将使用 QUEUE 和 ITERATIVE 方法（大多数 RECURSION 最终会使用 DFS）。这些数字表示在 BFS 中访问节点的顺序：
在深度优先搜索中，您从根开始，并尽可能地跟随树的一个分支，直到找到您要查找的节点或者您找到叶节点（没有子节点的节点）。如果你点击了一个叶子节点，那么你继续搜索最近的具有未探索子节点的祖先。
DFS 的一个例子
这是 DFS 的外观示例。我认为二叉树中的后序遍历将首先从叶级别开始工作。这些数字表示在 DFS 中访问节点的顺序：
DFS 和 BFS 的区别
比较 BFS 和 DFS，DFS 的最大优势在于它比 BFS 对内存的要求要低得多，因为不必在每个级别存储所有子指针。根据数据和您要查找的内容，DFS 或 BFS 都可能是有利的。
例如，给定一棵家谱，如果有人在树上寻找还活着的人，那么可以安全地假设那个人会在树的底部。这意味着 BFS 需要很长时间才能达到最后一个级别。然而，DFS 会更快地找到目标。但是，如果要寻找很久以前去世的家人，那么那个人会更接近树顶。然后，BFS 通常会比 DFS 更快。因此，两者的优势取决于数据和您正在寻找的内容。
另一个例子是 Facebook；对朋友的朋友的建议。我们需要直接的朋友来建议我们可以在哪里使用 BFS。可能是寻找最短路径或检测循环（使用递归），我们可以使用 DFS。
于 2015-02-13T08:49:52.017 回答
59
当树的深度可以变化时，广度优先搜索通常是最好的方法，您只需搜索树的一部分即可找到解决方案。例如，找到从起始值到最终值的最短路径是使用 BFS 的好地方。
当您需要搜索整个树时，通常使用深度优先搜索。它比 BFS 更容易实现（使用递归），并且需要更少的状态：虽然 BFS 需要您存储整个“边界”，但 DFS 只需要您存储当前元素的父节点列表。
于 2010-07-26T12:09:20.707 回答
34
DFS 比 BFS 更节省空间，但可能会进入不必要的深度。
他们的名字很能说明问题：如果有很大的广度（即大的分支因子），但深度非常有限（例如“移动”的数量有限），那么 DFS 可能比 BFS 更可取。
在 IDDFS 上
需要指出的是，还有一个鲜为人知的变体，它结合了 DFS 的空间效率，但（累积）BFS 的层序访问，是迭代加深深度优先搜索。该算法重新访问了一些节点，但它只贡献了一个渐近差异的常数因子。
于 2010-07-26T07:30:53.817 回答
21
当您作为程序员处理这个问题时，一个因素很突出：如果您使用递归，那么深度优先搜索更容易实现，因为您不需要维护包含尚未探索的节点的额外数据结构。
如果您在节点中存储“已经访问过”的信息，则这是对非定向图的深度优先搜索：
def dfs(origin): # DFS from origin:
origin.visited = True # Mark the origin as visited
for neighbor in origin.neighbors: # Loop over the neighbors
if not neighbor.visited: dfs(neighbor) # Visit each neighbor if not already visited
如果将“已访问”信息存储在单独的数据结构中：
def dfs(node, visited): # DFS from origin, with already-visited set:
visited.add(node) # Mark the origin as visited
for neighbor in node.neighbors: # Loop over the neighbors
if not neighbor in visited: # If the neighbor hasn't been visited yet,
dfs(neighbor, visited) # then visit the neighbor
dfs(origin, set())
将此与广度优先搜索进行对比，在这种搜索中，无论如何您都需要为尚未访问的节点列表维护一个单独的数据结构。
于 2012-03-13T17:56:59.633 回答
16
BFS 的一个重要优点是它可以用来找到未加权图中任意两个节点之间的最短路径。然而，我们不能将 DFS 用于相同的.
于 2015-12-11T23:08:43.017 回答
9
以下是对您所问问题的全面回答。
简单来说：
广度优先搜索（BFS）算法，从它的名字“Breadth”开始，通过节点的出边发现节点的所有邻居，然后通过它们的出边发现前面提到的邻居的未访问邻居，依此类推，直到所有访问从原始源可到达的节点（如果还有未访问的节点等，我们可以继续并采用另一个原始源）。这就是为什么如果边的权重是一致的，它可以用来找到从一个节点（原始源）到另一个节点的最短路径（如果有的话）。
深度优先搜索 (DFS) 算法，从它的名称“深度”开始，通过其出边发现最近发现的节点 x 的未访问邻居。如果没有来自节点 x 的未访问邻居，则算法回溯以发现从其发现节点 x 的节点的未访问邻居（通过其外边），依此类推，直到访问了从原始源可到达的所有节点（如果还有未访问的节点等，我们可以继续并采用另一个原始来源）。
BFS 和 DFS 都可能不完整。例如，如果一个节点的分支因子是无限的，或者对于支持的资源（内存）来说非常大（例如，当存储下一个要发现的节点时），那么即使搜索到的 key 可能在远处，BFS 也不完整来自原始来源的少数边缘。这种无限分支因子可能是因为从给定节点发现的无限选择（相邻节点）。如果深度是无限的，或者资源（内存）支持的深度非常大（例如，当存储下一个要发现的节点时），那么即使搜索到的键可以是原始源的第三个邻居，DFS 也不完整。这种无限深度可能是因为对于算法发现的每个节点，至少存在一个以前未访问过的新选择（相邻节点）。
因此，我们可以得出何时使用 BFS 和 DFS 的结论。假设我们正在处理可管理的有限分支因子和可管理的有限深度。如果搜索到的节点很浅，即在原始源的一些边之后可以到达，那么最好使用 BFS。另一方面，如果搜索到的节点很深，即在来自原始源的许多边之后可达，那么最好使用 DFS。
例如，在社交网络中，如果我们要搜索与特定人有相似兴趣的人，我们可以应用此人的 BFS 作为原始来源，因为这些人大多是他的直接朋友或朋友的朋友，即一个或两条边远。另一方面，如果我们要搜索与某个特定人的兴趣完全不同的人，我们可以应用此人的 DFS 作为原始来源，因为这些人大多会离他很远，即朋友的朋友的朋友.... 即边缘太多。
Applications of BFS and DFS can vary also because of the mechanism of searching in each one. For example, we can use either BFS (assuming the branching factor is manageable) or DFS (assuming the depth is manageable) when we just want to check the reachability from one node to another having no information where that node can be. Also both of them can solve same tasks like topological sorting of a graph (if it has). BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph. Also DFS, can be used for cycle detection in a graph.
In the end if we have infinite depth and infinite branching factor, we can use Iterative Deepening Search (IDS).
于 2019-05-08T19:52:39.963 回答
4
一些算法依赖于 DFS（或 BFS）的特定属性来工作。例如，用于查找 2 连通分量的 Hopcroft 和 Tarjan 算法利用了这样一个事实，即 DFS 遇到的每个已访问节点都位于从根到当前探索节点的路径上。
于 2010-07-26T14:13:31.660 回答
4
对于 BFS，我们可以考虑 Facebook 示例。我们从其他朋友的个人资料中收到从 FB 个人资料添加朋友的建议。假设 A->B，而 B->E 和 B->F，那么 A 会得到 E 和 F 的建议。他们必须使用 BFS 读取到第二级。DFS 更多地基于我们希望根据从源到目的地的数据进行预测的场景。正如已经提到的国际象棋或数独。一旦我在这里有所不同，我相信 DFS 应该用于最短路径，因为 DFS 将首先覆盖整个路径，然后我们可以决定最佳路径。但是由于 BFS 将使用贪婪的方法，所以它可能看起来是最短路径，但最终结果可能会有所不同。让我知道我的理解是否错误。
于 2017-02-18T20:19:22.527 回答
4
我认为这取决于您面临的问题。
- 简单图上的最短路径-> bfs
- 所有可能的结果-> dfs
- 在图上搜索（也将树、martix 视为图）-> dfs ....
于 2019-05-09T19:19:04.387 回答
2
根据 DFS 和 BFS 的性质。例如，当我们想找到最短路径时。我们通常使用 bfs，它可以保证“最短”。但是dfs只能保证我们能从这个点来达到那个点，不能保证“最短”。
于 2015-08-12T04:01:29.937 回答
2
因为深度优先搜索在处理节点时使用堆栈，所以 DFS 提供了回溯。因为广度优先搜索使用队列而不是堆栈来跟踪处理了哪些节点，所以 BFS 不提供回溯。
于 2017-05-22T17:39:30.613 回答
1
当树的宽度很大并且深度很低时使用DFS，因为递归堆栈不会溢出。当宽度很小时并且深度很大时使用BFS来遍历树。
于 2017-11-26T18:10:44.183 回答
0
这是证明 BFS 在某些情况下优于 DFS 的一个很好的例子。https://leetcode.com/problems/01-matrix/
如果正确实施，两种解决方案都应该访问距离比当前单元格 +1 更远的单元格。但是 DFS 效率低下并且重复访问同一个单元导致 O(n*n) 复杂度。
例如，
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
于 2017-06-01T06:11:24.577 回答