我理解DFS和BFS之间的区别,但是我想知道在选择DFS和BFS时应该考虑哪些因素。
比如对于非常深的树避免DFS,等等。
我理解DFS和BFS之间的区别,但是我想知道在选择DFS和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())
与此形成对比的是广度优先搜索,在广度优先搜索中,无论如何都需要为尚未访问的节点列表维护单独的数据结构。
其他回答
因为深度优先搜索在处理节点时使用堆栈,所以DFS提供回溯。由于宽度优先搜索使用队列而不是堆栈来跟踪正在处理的节点,BFS不提供回溯。
我认为这取决于你所面临的问题。
简单图上的最短路径-> BFS 所有可能的结果-> DFS 在图上搜索(将树,martix也视为图)-> 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())
与此形成对比的是广度优先搜索,在广度优先搜索中,无论如何都需要为尚未访问的节点列表维护单独的数据结构。
当树的深度可以变化时,宽度优先搜索通常是最好的方法,并且您只需要搜索树的一部分来寻找解决方案。例如,寻找从起始值到最终值的最短路径是使用BFS的好地方。
深度优先搜索通常用于需要搜索整个树的情况。它比BFS更容易实现(使用递归),并且需要更少的状态:BFS需要存储整个“边界”,DFS只需要存储当前元素的父节点列表。
For BFS, we can consider Facebook example. We receive suggestion to add friends from the FB profile from other other friends profile. Suppose A->B, while B->E and B->F, so A will get suggestion for E And F. They must be using BFS to read till second level. DFS is more based on scenarios where we want to forecast something based on data we have from source to destination. As mentioned already about chess or sudoku. Once thing I have different here is, I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best. But as BFS will use greedy's approach so might be it looks like its the shortest path, but the final result might differ. Let me know whether my understanding is wrong.