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

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

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

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

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

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

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

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

关于国际发展基金

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

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

深度优先搜索

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

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

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

广度优先搜索

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

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