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

当正确实现时，两个解决方案都应该访问比当前单元格+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,

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

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

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的水平顺序访问，是迭代深化深度优先搜索。该算法对一些节点进行了重访，但只贡献了一个常数因子的渐近差分。

BFS的一个重要优势是，它可以用于寻找未加权图中任意两个节点之间的最短路径。 然而，我们不能用DFS来做同样的事情。

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

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

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

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

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