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())
15 回答
这在很大程度上取决于搜索树的结构以及解决方案的数量和位置（也称为搜索项目） .
如果您知道解决方案离树的根不远，那么广度优先搜索（BFS）可能会更好 .
如果树很深并且解决方案很少，深度优先搜索（DFS）可能需要很长时间，但BFS可能会更快 .
如果树很宽，BFS可能需要太多内存，因此它可能完全不切实际 .
如果解决方案频繁但位于树的深处，BFS可能是不切实际的 .
如果搜索树非常深，则无论如何都需要限制深度优先搜索（DFS）的搜索深度（例如，使用迭代加深） .
但这些只是经验法则;你可能需要进行实验 .
很好的解释http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/
这是BFS的样子 . 这类似于Level Order Tree Traversal，我们将使用QUEUE和ITERATIVE方法（大多数RECURSION将以DFS结束） . 数字表示在BFS中访问节点的顺序：
在深度优先搜索中，从根开始，并尽可能地跟随树的一个分支，直到找到要查找的节点或者您到达叶节点（没有子节点的节点） . 如果您点击叶子节点，则继续搜索最近的祖先与未探测的子节点 .
这是DFS的外观示例 . 我认为二叉树中的后期遍历将首先从Leaf级别开始工作 . 数字表示在DFS中访问节点的顺序：
比较BFS和DFS，DFS的最大优点是它比BFS具有更低的内存要求，因为没有必要在每个级别存储所有子指针 . 根据数据和您要查找的内容，DFS或BFS可能是有利的 .
例如，给定一个家谱，如果一个人在树上寻找仍然活着的人，那么可以安全地假设该人将在树的底部 . 这意味着BFS需要很长时间才能达到最后一级 . 但是，DFS会更快地找到目标 . 但是，如果一个人正在寻找一个很久以前去世的家庭成员，那么这个人就会更接近树顶了 . 然后，BFS通常比DFS快 . 因此，两者的优势取决于数据和您正在寻找的内容 .
另一个例子是Facebook;对朋友之友的建议 . 我们需要直接的朋友来建议我们可以使用BFS的地方 . 可能是找到最短路径或检测周期（使用递归）我们可以使用DFS .
深度优先搜索
深度优先搜索通常用于模拟游戏（以及现实世界中类似游戏的情况） . 在典型的游戏中，您可以选择几种可能的操作之一 . 每种选择都会带来进一步的选择，每种选择都会导致进一步的选择，以此类推，形成一种不断扩展的树形图形 .
例如在像国际象棋这样的游戏中，当你决定做出什么动作时，你可以在心理上想象一个动作，然后你的对手的可能反应，然后是你的反应，等等 . 您可以通过查看哪个移动可以获得最佳结果来决定做什么 .
只有游戏树中的某些路径才能赢得胜利 . 有些会导致你的对手获胜，当你达到这样的结局时，你必须备份或回溯到前一个节点并尝试不同的路径 . 通过这种方式，您可以探索树，直到找到成功结束的路径 . 然后你沿着这条路走第一步 .
广度优先搜索
广度优先搜索具有一个有趣的属性：它首先找到距离起点一个边缘的所有顶点，然后是两个边缘的所有顶点，依此类推 . 如果您尝试找到从起始顶点到给定顶点的最短路径，这将非常有用 . 启动BFS，当找到指定的顶点时，您知道到目前为止您所跟踪的路径是该节点的最短路径 . 如果路径较短，BFS就已经找到了 .
广度优先搜索可用于在诸如BitTorrent之类的对等网络中找到邻居节点，用于寻找附近位置的GPS系统，用于在指定距离内找到人的社交网站以及类似的东西 .
当树的深度可以变化时，广度优先搜索通常是最好的方法，并且您只需要搜索树的一部分以获得解决方案 . 对于例如，找到从起始值到最终值的最短路径是使用BFS的好地方 .
当您需要搜索整个树时，通常会使用深度优先搜索 . 它比BFS更容易实现（使用递归），并且需要更少的状态：虽然BFS要求您存储整个“前沿”，但DFS仅要求您存储当前元素的父节点列表 .
DFS比BFS更节省空间，但可能会达到不必要的深度 .
他们的名字很明显：如果有一个很大的广度（即大分支因子），但深度非常有限（例如“移动”数量有限），那么DFS可能更适合BFS .
在IDDFS上
应该提到的是，有一个鲜为人知的变体结合了DFS的空间效率，但（累积地）BFS的水平顺序访问，是iterative deepening depth-first search . 该算法重新访问了一些节点，但它只是渐近差的常数因子 .
BFS的一个重要优点是它可以用于找到未加权图中任意两个节点之间的最短路径 . 鉴于we cannot use DFS for the same .
当您以程序员的身份处理这个问题时，一个因素突出：如果您正在使用递归，那么深度优先搜索将被实现，因为您不需要维护包含尚未探索的节点的其他数据结构 .
如果您在节点中存储“已访问过的”信息，这里是深度优先搜索非定向图：
如果将“已访问”信息存储在单独的数据结构中：
将此与广度优先搜索进行对比，无论如何，您需要为尚未访问的节点列表维护单独的数据结构 .
对于BFS，我们可以考虑Facebook的例子 . 我们收到建议，从其他朋友 Profiles 中添加FB Profiles 中的朋友 . 假设A-> B，而B-> E和B-> F，所以A将得到E和F的建议 . 他们必须使用BFS读到第二级 . DFS更基于我们想要根据从源到目的地的数据预测某些内容的场景 . 如前所述，国际象棋或数独游戏 . 一旦我在这里有所不同，我相信DFS应该用于最短路径，因为DFS将覆盖整个路径然后我们可以决定最好的 . 但是因为BFS将使用贪婪的方法，所以它看起来可能是最短路径，但最终结果可能会有所不同 . 让我知道我的理解是否错误 .
一些算法依赖于DFS（或BFS）的特定属性来工作 . 例如，用于查找2个连接组件的Hopcroft和Tarjan算法利用了DFS遇到的每个已访问节点位于从根到当前探索节点的路径上的事实 .
根据DFS和BFS的属性 . 例如，当我们想要找到最短路径时 . 我们通常使用bfs，它可以保证'最短' . 但是dfs只能保证我们能够从这一点来到可以达到那一点，不能保证'最短' .
由于Depth-First Searches在处理节点时使用堆栈，因此DFS提供了回溯 . 因为广度优先搜索使用队列而不是堆栈来跟踪处理的节点，所以BFS不提供回溯 .
当树宽度非常大且深度较低时，使用DFS作为递归堆栈不会溢出 . 当宽度较低且深度非常大以遍历树时使用BFS .
这是一个很好的例子来证明在某些情况下BFS比DFS更好 . https://leetcode.com/problems/01-matrix/
当正确实现时，两个解决方案都应该访问距离比当前单元1更远的单元 . 但是DFS效率低并且重复访问相同的单元，导致O（n * n）复杂度 .
例如，
这取决于它所使用的情况 . 每当我们遇到遍历图形的问题时，我们就会出于某种目的而这样做 . 当存在在未加权图中找到最短路径的问题，或者查找图是否为二分图时，我们可以使用BFS . 对于循环检测或任何需要回溯的逻辑问题，我们可以使用DFS .
这个问题有些陈旧，但一个很好的例子来自现代电子游戏“Bit Heroes” . 在一个典型的老板地牢中，你的目标是打败老板，之后你可以选择退出特定的地牢或继续探索战利品 . 但总的来说，老板远离你的产卵点 . 游戏提供了一个自动的地下城遍历功能，基本上可以让你的角色穿过地牢，遇到敌人 . 这是通过深度优先搜索算法实现的，因为目标是在回溯之前尽可能深入地牢 .