改进的 BFS 时间复杂度

Question

所以 BFS 的复杂度为 O(|V| + |E|) 当队列是这样实现的：

ENQUEUE(Q,source_vertex)
while Q != NULL
   u=DEQUEUE(Q)
   for each v in AdjacencyList[u]
     if v not yet visited
        Make v visited
        ENQUEUE(Q,v)

如果我修改代码以将 u 的邻接列表中的所有顶点添加到队列中，如下所示：

ENQUEUE(Q,source_vertex)
while Q != NULL
   u=DEQUEUE(Q)
   for each v in AdjacencyList[u]
      if v not finalized            
         ENQUEUE(Q,v)
   make u finalized

运行时间还会保持O(|V| + |E|)吗？

提前致谢。

Answer 1

据我了解，运行时复杂度也是 O(|V|+|E|)。第二个版本只是将 finalization 步骤（也可以称为 visiting）推迟到下一次迭代；递归调用的次数和顶点的顺序都没有改变。

Answer 2

假设您有一个由 n 个节点组成的集团（让我们将它们编号为 1、2、...、n，并假设邻接列表按此顺序存储它们）并且您运行修改后的算法从节点开始1. 节点 1 将使节点 2、3、...、n 入队，总共执行 Θ(n) 项工作。队列现在看起来像这样：

2, 3, 4, ..., n

当您随后处理节点 2 时，它将查看其所有边以进行 Θ(n) 更多工作，然后将节点 3、4、5、...、n 放入队列中。我们的队列现在看起来像这样：

3, 4, 5, ..., n, 3, 4, 5, ..., n

我们现在处理节点 3，它查看其所有边以进行 Θ(n) 工作，然后将节点 4、5、6、...、n 入队，因此我们的队列如下所示：

4, 5, 6, ..., n, 3, 4, 5, ..., n, 4, 5, 6, ..., n

这里的模式是我们最终将图中每个节点的许多副本排入队列。事实上，随着时间的推移，我们最终会在队列中得到总共 Θ(n²) 个节点，并且我们对每个节点执行 Θ(n) 个工作。这意味着该图完成的总工作量为 Θ(n³)，超过了原始 BFS 实现的 O(m + n) 时间限制。

因此，这个新实现可能比常规 BFS 渐近地慢。

Answer 3

让我们更改您的算法以将边添加到队列中（因为这就是您正在做的隐式操作 - 除非您在将它添加到队列而不是整个边时仅查看相反的顶点）：

ENQUEUE( Q,(NULL->source_vertex) )            # start with a dummy edge
WHILE Q != NULL
  (s->u)=DEQUEUE(Q)
  for each (u->v) in AdjacencyList[u]   
    if v not finalized
      ENQUEUE(Q,(u->v))
  make u finalized

每条边将被考虑入队两次 (u->v) 和 (v->u)。当访问边 u 的第一个顶点时，每个相邻边将被放入队列，然后 u 完成。当访问 v 时，将考虑边 (v->u)，但由于 u 已经完成，因此不会添加到队列中；所以每条边只会被排队一次（在一个方向而不是在另一个方向）。

该算法的问题在于它不检查它要处理的顶点是否已经完成，而是会为队列中的每条边重新处理它，再次遍历所有相邻边，从而使您的算法 O(|V||E|)（而不是 O(|V| + |E|)）。

一个简单的修复方法是：

ENQUEUE( Q,(NULL->source_vertex) )            # start with a dummy edge
WHILE Q != NULL
  (s->u)=DEQUEUE(Q)
  if u not finalized
    for each (u->v) in AdjacencyList[u]
      if v not finalized
        ENQUEUE(Q,(u->v))
    make u finalized

此外，您的算法的两个版本都将从一个顶点开始，然后处理同一连通分量内的每条边 - 但是它们只会在连通图上执行完整的 BFS。如果您有多个断开连接的组件，那么您需要使用：

for each source_vertex in Graph
  if source_vertex not visited/finalised
    call your_algorithm( source_vertex )

这将是 O(|V| + |E|) 并会访问所有顶点，无论图形是否连接。

改进的 BFS 时间复杂度

Modified BFS Time Complexity

algorithm

graph-theory

graph-algorithm

breadth-first-search