深度优先搜索

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

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

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

广度优先搜索

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

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

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

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

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

来自 http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

一个BFS的例子

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

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

DFS的一个例子

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

DFS和BFS的区别

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

For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.

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

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

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

If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

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

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