DFS比BFS更节省空间，但可能会深入到不必要的深度。

它们的名字揭示了:如果有很大的广度(即大的分支因子)，但深度非常有限(例如有限的“移动”数量)，那么DFS可能比BFS更受欢迎。

在IDDFS

应该提到的是，有一个不太为人所知的变体，它结合了DFS的空间效率，但(累计)BFS的层次顺序访问，是迭代深化深度优先搜索。该算法对一些节点进行了重访，但只贡献了一个常数因子的渐近差分。

这在很大程度上取决于搜索树的结构以及解的数量和位置(也就是搜索项)。

• 如果你知道一个解离树的根不远，a 宽度优先搜索(BFS)可能更好

如果树非常深，解决方案很少，深度优先搜索 (DFS)可能需要非常长的时间，但BFS可能更快

• 如果树非常宽，BFS可能需要太多的内存，因此它将使用 可能完全不切实际

如果解是频繁的，但位于树的深处，则可能是BFS 不切实际的。< / p >

• 如果搜索树很深，则需要限制搜索 深度优先搜索(depth for depth first search, DFS) 迭代深化)。< / p >

但这些只是经验法则;你可能需要尝试一下。

我认为在实践中，你通常不会以纯粹的形式使用这些算法。可能会有一些启发式方法，有助于首先探索搜索空间中有希望的部分，或者您可能希望修改搜索算法，以便能够有效地并行化它。

当树的深度可以变化时，宽度优先搜索通常是最好的方法，并且您只需要搜索树的一部分来寻找解决方案。例如，寻找从起始值到最终值的最短路径是使用BFS的好地方。

深度优先搜索通常用于需要搜索整个树的情况。它比BFS更容易实现(使用递归)，并且需要更少的状态:BFS需要存储整个“边界”，DFS只需要存储当前元素的父节点列表。

一些算法依赖于DFS(或BFS)的特定属性来工作。例如，用于查找2连接组件的Hopcroft和Tarjan算法利用了这样一个事实，即DFS遇到的每个已经访问过的节点都位于从根节点到当前探索的节点的路径上。

当你作为一个程序员处理这个问题时，有一个因素很突出:如果你使用递归，那么深度优先搜索是更简单的来实现的，因为你不需要维护一个包含尚未探索的节点的额外数据结构。

如果你在节点中存储“已经访问过”的信息，下面是深度优先搜索非面向图:

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())

与此形成对比的是广度优先搜索，在广度优先搜索中，无论如何都需要为尚未访问的节点列表维护单独的数据结构。

漂亮的解释来自 http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/ < / p >

一个BFS的例子

这里有一个BFS的例子。这类似于级别顺序树遍历，其中我们将使用迭代方法的队列(大多数递归将最终使用DFS)。数字表示BFS中节点被访问的顺序:

在深度优先搜索中，从根开始，尽可能地跟随树的一个分支，直到找到要查找的节点或找到叶节点(没有子节点)。如果您选中了一个叶节点，那么您将继续在最近的具有未探索的子节点的父节点上搜索。

DFS的一个例子

下面是一个DFS的示例。我认为二叉树中的后序遍历将首先从叶层开始工作。数字表示DFS中节点被访问的顺序:

DFS和BFS的区别

比较BFS和DFS, DFS的最大优势是它的内存需求比BFS低得多，因为它不需要在每一层存储所有的子指针。根据数据和您正在寻找的内容，DFS或BFS都可能是有利的。

例如，给定一棵家谱，如果有人在树上寻找还活着的人，那么可以肯定这个人会在树的最下面。这意味着BFS需要很长时间才能达到最后一个水平。然而，DFS会更快地找到目标。但是，如果一个人在寻找一个很久以前去世的家庭成员，那么这个人会更接近树的顶部。那么，BFS通常会比DFS快。所以，这两种方法的优势取决于数据和你想要的东西。

另一个例子是Facebook;关于朋友的朋友的建议。我们需要直接的朋友建议我们在哪里可以使用BFS。可能是寻找最短路径或检测周期(使用递归)，我们可以使用DFS。

根据DFS和BFS的属性。 例如，当我们要求最短路径时。 我们通常使用bfs，它可以保证“最短”。 但是DFS只能保证我们可以从这一点可以到达那一点，不能保证‘最短’

深度优先搜索

深度优先搜索通常用于模拟游戏(以及现实世界中的类似游戏场景)。在典型的游戏中，你可以从几种可能的行动中选择一种。每个选择都会引出更多的选择，每个选择又会引出更多的选择，如此循环往复，形成一个不断扩大的可能性树形图。

例如，在国际象棋和井字游戏中，当你决定走哪一步时，你可以在脑海中想象一步，然后是对手可能的反应，然后是你的反应，等等。你可以通过观察哪一步会带来最好的结果来决定做什么。

在游戏树中只有一些路径能够引导你获胜。有些会导致你的对手获胜，当你到达这样的结局时，你必须后退或回溯到前一个节点，并尝试不同的路径。通过这种方式，您可以探索树，直到找到一条具有成功结论的路径。然后沿着这条路迈出第一步。

广度优先搜索

宽度优先搜索有一个有趣的特性:它首先找到距离起点一条边的所有顶点，然后是距离起点两条边的所有顶点，依此类推。如果你试图找到从起始顶点到给定顶点的最短路径，这是很有用的。你开始一个BFS，当你找到指定的顶点时，你知道你到目前为止跟踪的路径是到该节点的最短路径。如果有更短的路径，BFS早就找到了。

宽度优先搜索可用于在BitTorrent等对等网络中查找相邻节点，GPS系统用于查找附近位置，社交网站用于查找指定距离内的人等等。

因为深度优先搜索在处理节点时使用堆栈，所以DFS提供回溯。由于宽度优先搜索使用队列而不是堆栈来跟踪正在处理的节点，BFS不提供回溯。

这是一个很好的例子，说明BFS在某些情况下优于DFS。https://leetcode.com/problems/01-matrix/

例如,

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,

当树的宽度非常大，深度很低时，使用DFS作为递归堆栈不会溢出。当宽度很低而深度很大时使用BFS遍历树。

以下是对你的问题的全面回答。

简单来说:

广度优先搜索(BFS)算法，从它的名字“广度”，通过节点的外边发现一个节点的所有邻居，然后通过前面提到的邻居的外边发现未访问的邻居，以此类推，直到所有从原始源可到达的节点都被访问(如果还有剩余的未访问节点，我们可以继续获取另一个原始源，依此类推)。这就是为什么它可以用来找到从一个节点(原始源)到另一个节点的最短路径(如果有的话)，前提是边的权值是一致的。

深度优先搜索(deep First Search, DFS)算法，顾名思义，是通过最近发现的节点x的外缘发现其未访问的邻居。如果节点x没有未访问的邻居，算法将回溯到发现节点x的节点的未访问邻居(通过其外边)，依此类推，直到访问了从原始源可到达的所有节点(如果还有剩余的未访问节点，则可以继续获取另一个原始源，依此类推)。

因此，我们可以得出什么时候使用BFS和DFS。假设我们正在处理一个可管理的有限分支因子和一个可管理的有限深度。如果搜索的节点很浅，即在原始源的一些边之后可以到达，那么最好使用BFS。另一方面，如果搜索的节点较深，即从原始源处经过大量边后可以到达，那么最好使用DFS。

最后，如果我们有无限的深度和无限的分支因子，我们可以使用迭代深化搜索(IDS)。

我认为这取决于你所面临的问题。

1. 简单图上的最短路径-> BFS
2. 所有可能的结果-> DFS
3. 在图上搜索(将树，martix也视为图)-> DFS 李…< / >