我理解DFS和BFS之间的区别,但是我想知道在选择DFS和BFS时应该考虑哪些因素。

比如对于非常深的树避免DFS,等等。


当前回答

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

其他回答

当树的宽度非常大,深度很低时,使用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())

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

我认为这取决于你所面临的问题。

简单图上的最短路径-> BFS 所有可能的结果-> DFS 在图上搜索(将树,martix也视为图)-> DFS ....

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

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