algorithm - 广度优先搜索与深度优先搜索

Question

谁能简单解释一下BFS和DFS？
我想了解何时更喜欢 BFS 而不是 DFS。

Answer 1

BFS和DFS都是图遍历算法，它们的区别在于各自算法遍历图的方式。

DFS，假设您有以下图形，我们想从节点 1 开始遍历:

          1
         / \
        2   3
       / \   \
      4   5   6

DFS的意思是深度优先搜索，所以会这样遍历图:

• 从节点 1 开始，然后寻找它的子节点。它找到节点 2。
• 转到节点 2 然后寻找它的子节点。它找到节点 4。
• 转到节点 4 然后它发现它没有 child 。
• 再次Up 到节点2 并查看它的其他子节点。它找到节点 5。
• 转到节点 5 然后它发现它没有 child 。
• 再次上到节点2，发现它没有更多的 child 。
• 上到节点 1 然后寻找它的 child 。它找到节点 3。
• 转到节点 3 然后寻找它的子节点。它找到节点 6。
• 转到节点 6 并发现它没有子节点。
• 上到节点 3 并发现它没有更多的 child 。
• 向上到节点1，发现它没有更多的 child ，因此图遍历到此结束。

如果您在这里注意到该算法如何首先进入深度，那么一旦它发现节点 2 是节点 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)并寻找这个 child (没有 child )[没有下一级] .
• 然后图遍历到此结束。

你可以在这里意识到一个节点(下一级)的直接子节点总是离它最近的节点，因此使用 BFS 优于 DFS 的优势在于它可以保证你从节点 x 到节点 y 使用可能的最短路径。

但请注意，BFS 算法无法为您找到所有类型图的最短路径。我在这个例子中提到的图是未加权图(所有边/路径都相同的图)。如果您的图形是加权的(边/路径具有权重但不相同)，那么您必须使用另一种考虑到这一点的算法(例如 Dijkstra )。