7

关于广度优先搜索的Wikipedia 文章列出了图上广度优先搜索的两个时间复杂度：O(|E|) 和 O(b d )。但是，在页面的后面，它只列出了 O(|E|)。

为什么有两个不同的运行时？哪一个是正确的？

4

1 回答 1

16

两种时间复杂度都是正确的，但在不同情况下用于测量相对于两个不同数量的时间复杂度。这与广度优先搜索算法通常是指在不同上下文中使用的两种不同的相关算法有关。

在一个上下文中，BFS 是一种算法，给定一个图和图中的一个起始节点，通过首先访问距离 0、距离 1、距离 2 等处的所有节点，访问从起始节点可到达的每个节点，直到所有节点被访问。这将访问图中的每个节点，并且在这样做的过程中，每个节点和边最多探索一次（在有向情况下）或两次（在无向情况下）。通过使用队列来跟踪接下来要探索的节点并使用适当的簿记，运行时间将是 O(|E| + |V|)（如果进一步优化，它将是 O(|E|)）。

在不同的上下文中，BFS 是一种搜索算法，用于查找从图中的某个起始节点到图中的目标节点的最短路径。在这种情况下，算法一发现目标节点就停止运行。这意味着运行时间取决于目标节点与源节点的距离。该距离又取决于图的结构。如果图是密集连接的，则节点不可能离得那么远，如果图是稀疏的，则节点可能会非常遥远。在这种情况下，通常添加一个称为“分支因子” b的参数，它描述了与任何节点相邻的平均或最大边数。这意味着

  • 距离起始节点 0 处有一个节点。
  • 距起始节点 1处最多有b个节点。
  • 距起始节点 2处最多有b 2个节点。
  • ...
  • 与起始节点距离为 k处最多有b k个节点。

如果我们假设目标节点与起始节点的距离为d，那么 BFS 在搜索过程中最多会访问 b 0 + b 1 + ... + b d = O(b d ) 个节点，花费 O(b)他们每个人的时间。因此，总运行时间将为 O(b d )。

总之：

  • O(|E|) 的运行时间通常用于在用于探索整个图时讨论算法。
  • O(b d ) 的运行时间通常在讨论算法时用于在图中查找特定节点时使用。

希望这可以帮助！

于 2013-11-04T00:09:27.123 回答