什么时候可以使用DFS vs BFS？
我了解DFS（深度优先search）和BFS（广度优先search）之间的差异，但是我有兴趣知道什么时候使用它们更实用？
任何人都可以举例说明DFS如何超越BFS，反之亦然？
这很大程度上取决于search树的结构以及解决scheme的数量和位置（又名search项目）。
- 如果你知道一个解决scheme离树的根部不远，那么广度优先search（BFS）可能会更好。
-
如果树很深并且解决scheme很less，深度优先search（DFS）可能需要很长时间，但是BFS可能会更快。
-
如果树很宽，BFS可能需要太多的内存，所以这可能是完全不切实际的。
-
如果解决scheme频繁，但位于树的深处，BFS可能是不切实际的。
- 如果search树非常深，则无论如何（例如迭代加深），您都需要限制深度优先search（DFS）的search深度。
但这些只是经验法则。 你可能需要试验。
从http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/的很好的解释;
BFS的一个例子
下面是一个BFS的例子。 这就像Level Order Tree Traversal，我们将使用QUEUE和ITERATIVE方法（大多数RECURSION将以DFS结束）。 数字表示在BFS中访问节点的顺序：
在进行深度优先search时，首先从根开始，然后尽可能跟随树的某个分支，直到find您正在查找的节点或者您击中了一个叶节点（没有子节点的节点）。 如果您击中叶节点，则继续在最近的祖先处search未探索的子节点。
DFS的一个例子
下面是DFS的一个例子。 我认为在二叉树中的顺序遍历将首先从叶级开始工作。 数字表示在DFS中访问节点的顺序：
DFS和BFS之间的区别
比较BFS和DFS，DFS的一大优点是它的内存要求比BFS低得多，因为不需要在每个级别存储所有的子指针。 根据数据和你在找什么，DFS或BFS可能是有利的。
例如，假如有人在树上寻找一个仍然活着的人，那么给定一棵家族树，那么假定这个人将在树的底部是安全的。 这意味着BFS需要很长时间才能达到最后的水平。 但是，DFS会更快地find目标。 但是，如果一个人正在寻找一个很久以前去世的家庭成员，那么这个人就会更接近树顶。 那么，BFS通常会比DFS更快。 所以，根据数据和您要查找的内容，其优点也会有所不同。
另一个例子是Facebook; 对朋友的build议。 我们需要直接的朋友提供build议，我们可以使用BFS。 可能是find最短path或检测周期（使用recursion）我们可以使用DFS。
深度优先search
深度优先search通常用于游戏的模拟（和现实世界中的类似游戏的情况）。 在典型的游戏中，您可以select几种可能的操作之一。 每个select导致进一步的select，每个select导致进一步的select，等等进入一个不断扩大的树形图的可能性。
例如，在像国际象棋，井字棋这样的游戏中，当你决定要做什么动作的时候，你可以在思维上想象一个动作，然后你的对手可能的反应，然后你的反应，等等。 您可以通过查看哪个移动导致最佳结果来决定要做什么。
在游戏树中只有一些path导致你的胜利。 有些会导致对手获胜，当你达到这样的结局时，你必须备份或回溯到前一个节点并尝试不同的path。 通过这种方式，你可以探索这棵树，直到你find一条成功的path。 然后你沿这条路走了第一步。
广度优先search
广度优先search具有一个有趣的特性：它首先find离开始点一个边的所有顶点，然后find两个边相离的所有顶点，依此类推。 如果您正在尝试查找从起始顶点到给定顶点的最短path，这非常有用。 您启动一个BFS，并且当您find指定的顶点时，您知道到目前为止所跟踪的path是该节点的最短path。 如果path较短，BFS就已经find了。
广度优先search可用于在BitTorrent等对等networking中查找邻居节点，查找附近位置的GPS系统，在指定距离内查找人员的社交网站等等。
宽度优先search通常是树的深度可以变化的最佳方法，并且您只需要search树的部分解决scheme。 例如，find从起始值到最终值的最短path是使用BFS的好地方。
当您需要search整个树时，深度优先search是常用的。 实现（使用recursion）比BFS更容易，并且需要更less的状态：虽然BFS需要存储整个“边界”，但DFS只需要存储当前元素的父节点列表。
DFS比BFS更具空间效率，但可能进入不必要的深度。
他们的名字揭示：如果有一个很大的广度（即大的分支因子），但深度非常有限（例如有限的“移动”数量），那么DFS更适合BFS。
在IDDFS上
需要说明的是，还有一个不太为人所知的结合DFS空间效率的变体，但是（累计地）BFS的层次访问是迭代深化的深度优先search 。 这个algorithm重新访问了一些节点，但它只贡献了渐近差的一个常数因子。
当你作为一个程序员来解决这个问题时，有一个因素很突出：如果你使用的是recursion，那么深度优先search更容易实现，因为你不需要维护包含尚未探索的节点的额外数据结构。
如果您要在节点中存储“已访问”信息，则可以先深入search非面向图：
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(next) # 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(node, visited) # then visit the neighbor dfs(origin, set())
将此与广度优先search进行对比，无论您需要为尚未访问的节点列表维护一个单独的数据结构。
BFS的一个重要优点是它可以用来find未加权图中任意两个节点之间的最短path。 而我们不能使用DFS 。
一些algorithm依赖于DFS（或BFS）的特定属性来工作。 例如，用于查找2连接组件的Hopcroft和Tarjanalgorithm利用了DFS遇到的每个已经访问的节点位于从根节点到当前探索节点的path上的事实。
对于BFS，我们可以考虑Facebook的例子。 我们收到来自其他朋友档案添加FB档案的朋友的build议。 假设A-> B，而B-> E和B-> F，则A将得到E和F的build议。他们必须使用BFS读取到第二级。 DFS更多地基于我们想要基于从源到目的地的数据来预测某些事物的场景。 正如已经提到的国际象棋或数独。 一旦我在这里有不同的东西，我相信DFS应该用于最短path，因为DFS将首先覆盖整个path，然后我们可以决定最好的。 但是由于BFS会使用贪婪的方法，所以可能会看起来像最短path，但最终的结果可能会有所不同。 让我知道我的理解是否错误。
根据DFS和BFS的特性。 例如，我们想要find最短的path。 我们通常使用bfs，它可以保证“最短”。 但是dfs只能保证我们可以从这个angular度来实现这一点，不能保证“最短”。
由于深度优先search在处理节点时使用堆栈，因此使用DFS提供回溯。 因为广度优先search使用队列而不是堆栈来跟踪哪些节点被处理，所以不向BFS提供回溯。
这是certificate在某些情况下BFS比DFS更好的一个很好的例子。 https://leetcode.com/problems/01-matrix/
如果正确实施，两种解决scheme都应访问比当前单元格+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,
这个问题有些古怪，但是现代电子游戏“英雄”就是一个很好的例子。 在一个典型的老板地下城里，你的目标是击败老板，之后你可以select退出那个特定的地下城，或继续探索它的掠夺。 但总的来说，老板远不及你的重生点。 游戏提供了一个自动的地下城遍历function，基本上把你的angular色穿过地下城，遇到敌人。 这是通过深度优先searchalgorithm实现的，因为目标是在回溯之前尽可能深入地下城。
