什么时候使用深度优先搜索(DFS)与广度优先搜索(BFS)是否可行？

Question

我理解DFS和BFS之间的区别,但是我很想知道何时使用一个比另一个更实用？

任何人都可以举例说明DFS如何胜过BFS,反之亦然？

Answer 1

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

• 如果您知道解决方案离树的根不远,那么广度优先搜索(BFS)可能会更好.

• 如果树很深并且解决方案很少,深度优先搜索(DFS)可能需要很长时间,但BFS可能会更快.

• 如果树很宽,BFS可能需要太多内存,所以它可能完全不切实际.

• 如果解决方案频繁但位于树的深处,那么BFS可能是不切实际的.

• 如果搜索树非常深,则无论如何都需要限制深度优先搜索(DFS)的搜索深度(例如,使用迭代加深).

但这些只是经验法则; 你可能需要进行实验.

Answer 2

深度优先搜索

深度优先搜索通常用于模拟游戏(以及现实世界中类似游戏的情况).在典型的游戏中,您可以选择几种可能的操作之一.每种选择都会导致进一步的选择,每种选择都会导致进一步的选择,等等,形成一种不断扩展的树形图形.

例如在像国际象棋这样的游戏中,当你决定做出什么样的动作时,你可以在心理上想象一个动作,然后你的对手的可能反应,然后是你的反应,等等.您可以通过查看哪种移动可以获得最佳结果来决定做什么.

只有游戏树中的某些路径才能赢得胜利.有些会导致你的对手获胜,当你达到这样的结局时,你必须备份或回溯到前一个节点并尝试不同的路径.通过这种方式,您可以探索树,直到找到成功结束的路径.然后沿着这条路径前进.

广度优先搜索

广度优先搜索具有一个有趣的属性:它首先找到距起点一个边缘的所有顶点,然后找到两个边缘的所有顶点,依此类推.如果您试图找到从起始顶点到给定顶点的最短路径,这将非常有用.您启动BFS,当您找到指定的顶点时,您知道到目前为止您已跟踪的路径是该节点的最短路径.如果路径较短,BFS就已经找到了.

广度优先搜索可用于查找邻居节点的点对点像BitTorrent网络,GPS系统找到附近的地点,社交网站找人在规定的距离之类的东西.

Answer 3

来自http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/的精彩解释

BFS的一个例子

这是BFS外观的一个例子.这类似于Level Order Tree Traversal,我们将使用QUEUE和ITERATIVE方法(大多数RECURSION将以DFS结束).数字表示在BFS中访问节点的顺序:

在深度优先搜索中,从根开始,并尽可能地跟随树的一个分支,直到找到您要查找的节点或者您到达叶节点(没有子节点的节点).如果您点击叶子节点,则继续搜索最近的祖先与未探测的子节点.

DFS的一个例子

这是DFS的外观示例.我认为二叉树中的发布顺序遍历将首先从Leaf级别开始工作.数字表示在DFS中访问节点的顺序:

DFS和BFS之间的差异

比较BFS和DFS,DFS的一大优势是它比BFS具有更低的内存要求,因为没有必要在每个级别存储所有子指针.根据数据和您要查找的内容,DFS或BFS可能是有利的.

例如,给定一个家谱,如果一个人在树上寻找仍然活着的人,那么可以安全地假设这个人将在树的底部.这意味着BFS需要很长时间才能达到最后一级.但是,DFS会更快地找到目标.但是,如果一个人正在寻找一个很久以前去世的家庭成员,那么这个人就会更接近树顶了.然后,BFS通常比DFS快.因此,两者的优势取决于数据和您正在寻找的内容.

另一个例子是Facebook; 对朋友之友的建议.我们需要直接的朋友来建议我们可以使用BFS.可能是找到最短路径或检测周期(使用递归)我们可以使用DFS.

Answer 4

广度优先搜索通常是当树的深度可以改变的最佳方法,你只需要搜索树的一部分的解决方案.例如,当发现到最终值从初值的最短路径是使用BFS的好地方.

当您需要搜索整个树时,通常会使用深度优先搜索.它比BFS更容易实现(使用递归),并且需要更少的状态:虽然BFS要求您存储整个"前沿",但DFS只需要存储当前元素的父节点列表.

Answer 5

DFS比BFS更节省空间,但可能会达到不必要的深度.

他们的名字很明显:如果有一个很大的广度(即大分支因子),但深度非常有限(例如"移动"数量有限),那么DFS可能更适合BFS.

在IDDFS上

应该提到的是,有一个鲜为人知的变体结合了DFS的空间效率,但(累积地)BFS的水平顺序访问,是迭代深度深度优先搜索.该算法重新访问了一些节点,但它只是渐近差的常数因子.

Answer 6

当您以程序员的身份处理这个问题时,一个因素突出:如果您使用递归,那么深度优先搜索更容易实现,因为您不需要维护包含尚未探索的节点的其他数据结构.

如果您在节点中存储"已访问过的"信息,这里是深度优先搜索非定向图:

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

将此与广度优先搜索进行对比,无论如何,您需要为尚未访问的节点列表维护单独的数据结构.

Answer 7

BFS的一个重要优点是它可以用于找到未加权图中任意两个节点之间的最短路径.然而,我们不能使用DFS.

Answer 8

我认为这取决于你面临什么问题。

1. 简单图上的最短路径 -> bfs
2. 所有可能的结果 -> dfs
3. 在图上搜索（将树、martix也视为图）-> dfs ....

Answer 9

The following is a comprehensive answer to what you are asking.

In simple terms:

Breadth First Search (BFS) algorithm, from its name "Breadth", discovers all the neighbours of a node through the out edges of the node then it discovers the unvisited neighbours of the previously mentioned neighbours through their out edges and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth). That's why it can be used to find the shortest path (if there is any) from a node (origional source) to another node if the weights of the edges are uniform.

Depth First Search (DFS) algorithm, from its name "Depth", discovers the unvisited neighbours of the most recently discovered node x through its out edges. If there is no unvisited neighbour from the node x, the algorithm backtracks to discover the unvisited neighbours of the node (through its out edges) from which node x was discovered, and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth).

Both BFS and DFS can be incomplete. For example if the branching factor of a node is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then BFS is not complete even though the searched key can be at a distance of few edges from the origional source. This infinite branching factor can be because of infinite choices (neighbouring nodes) from a given node to discover. If the depth is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then DFS is not complete even though the searched key can be the third neighbor of the origional source. This infinite depth can be because of a situation where there is, for every node the algorithm discovers, at least a new choice (neighbouring node) that is unvisited before.

Therefore, we can conclude when to use the BFS and DFS. Suppose we are dealing with a manageable limited branching factor and a manageable limited depth. If the searched node is shallow i.e. reachable after some edges from the origional source, then it is better to use BFS. On the other hand, if the searched node is deep i.e. reachable after a lot of edges from the origional source, then it is better to use DFS.

For example, in a social network if we want to search for people who have similar interests of a specific person, we can apply BFS from this person as an origional source, because mostly these people will be his direct friends or friends of friends i.e. one or two edges far. On the other hand, if we want to search for people who have completely different interests of a specific person, we can apply DFS from this person as an origional source, because mostly these people will be very far from him i.e. friend of friend of friend.... i.e. too many edges far.

Applications of BFS and DFS can vary also because of the mechanism of searching in each one. For example, we can use either BFS (assuming the branching factor is manageable) or DFS (assuming the depth is manageable) when we just want to check the reachability from one node to another having no information where that node can be. Also both of them can solve same tasks like topological sorting of a graph (if it has). BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph. Also DFS, can be used for cycle detection in a graph.

In the end if we have infinite depth and infinite branching factor, we can use Iterative Deepening Search (IDS).

Answer 10

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

Answer 11

对于BFS,我们可以考虑Facebook的例子.我们收到来自其他朋友个人资料的FB个人资料中添加朋友的建议.假设A-> B,而B-> E和B-> F,所以A将得到E和F的建议.他们必须使用BFS读到第二级.DFS更基于我们想要根据从源到目的地的数据预测某些内容的场景.如前所述,国际象棋或数独游戏.一旦我在这里有不同的东西,我相信DFS应该用于最短路径,因为DFS将覆盖整个路径然后我们可以决定最好的.但是因为BFS会使用贪婪的方法,所以看起来它可能是最短路径,但最终结果可能会有所不同.让我知道我的理解是否错误.