广度首先搜索与深度第一次搜索

Question

任何人都可以对BFS和DFS提供简单的解释？
我想了解何时更喜欢BF而不是DFS。

Answer 1

bfs和dfs都是遍历算法的图形，它们之间的差异是每种算法遍历图形的方式。

dfs ，想象一下您有以下图表，我们想开始从节点1：

开始遍历

          1
         / 
        2   3
       /    
      4   5   6

dfs表示深度第一次搜索，因此它将以这种方式遍历图：

• 从节点1开始，然后寻找其孩子。它找到了节点2。
• 转到节点2，然后寻找孩子。它找到了节点4。
• 转到节点4，然后发现它没有孩子。
• 再次将Up转到节点2，然后查看其他孩子。它找到了节点5。
• 转到节点5，然后发现它没有孩子。
• 再次上升到节点2，发现它没有更多的孩子。
• 上升到节点1，然后寻找孩子。它找到节点3。
• 转到节点3，然后寻找孩子。它找到节点6。
• 转到节点6，发现它没有孩子。
• 上升到节点3，发现它没有更多的孩子。
• 上升到节点1，发现它没有更多的孩子，因此遍历遍历已经完成。

如果您在这里注意到此算法如何在深度首先中进行，因此一旦发现Node 2是Node 1的孩子，它就去了它并开始寻找孩子，而无需关心其余的孩子在此时间点，节点1（节点3）的子女，然后进入最深可能的节点（节点4， 5）之后，它开始使用Up寻找节点1的其他孩子。

。

另一方面，请考虑我们要使用 bfs 算法遍历同一图。当使用 bfs 时，您开始将图节点视为级别时，每个级别都比其相对于您开始从中穿越的节点后的级别更接近。这意味着：

          1         (level 0)
         / 
        2   3       (level 1)
       /    
      4   5   6     (level 2)

遍历图的遍历将是：

• 从节点1开始，然后寻找其孩子（节点2，3）[下一个级别]。
• 1级的遍历节点（2，3）并寻找他们的孩子（节点4，5，6）[下一个级别]。
• 2级的遍历节点（4，5，6）并寻找这个孩子（没有孩子）[没有下一个级别]。
• 然后在这一点上绘制遍历结束。

您可以在这里意识到节点的直接子女（下一个级别）始终是最接近的节点，因此，使用BFS优于DFS，它可以保证您从节点x到达节点y使用最短路径。

但是请注意，BFS算法找不到所有类型的图形的最短路径。我在此示例中提到的图是未加权的图（其中所有边/路径相同的图）。如果您的图形是加权的（边缘/路径具有权重而不是相同），则必须使用另一种考虑到这一点的算法（例如Dijkstra）。