graph-algorithm - BFS为什么要求最短路径？

Question

BFS has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node.

如何验证此属性？为什么在 DFS 的情况下不持有这样的属性(property)？

Answer 1

要回答您的问题，您应该首先从一般意义上了解 BFS 和 DFS 的工作原理。

考虑一个二叉搜索树，它只是一个非常简单的图形，如下所示:

        *a
       /  \
    *b     *c
   /  \   /  \
  *d  *e *f   *g

广度优先搜索 (BFS)，顾名思义，将首先探索距离源节点最近的节点。假设您从节点 *a 开始搜索，BFS 算法将首先探索 *b，然后是 *c，然后是 *d、*e、*f、*g。

深度优先搜索 (DFS) 另一方面，深度优先。从源节点 *a 开始，您将展开 *b，然后是 *d、*e(直到几乎到达终点)。

因此，声明:

... the first time a node is visited is the shortest path to that node from the source node

假设，当 BFS 运行时，您访问了节点 *b。这确实是从源节点到节点*b 的最短路径，因为 BFS 具有总是先探索距离源节点最近的节点的属性。

类似的概念可以应用于更复杂的图形。它们的工作原理相同。

希望对您有所帮助!干杯!