algorithm - 广度优先搜索的执行时间

Question

我正在研究广度优先搜索的算法，如下:

BFS(G,s)
 for each u ∈ V\ {s}
     color(u)=white
     d(u)=oo
     π(u)=NIL
 color(s)=GRAY
 d(s)=0
 π(s)=NIL
 Q=∅
 ENQUEUE(Q,s)
 while (Q!=∅)
    u=DEQUEUE(Q)
    for each v ∈ Adj(u)
         if (color(v)=white)
             color(v)=GRAY
             d(v)=d(u)+1
             π(v)=u
             ENQUEUE(Q,v)
    color(v)=BLACK

我以为是这样的: 第一个 for 循环的时间复杂度是 O(V)。 while循环的时间复杂度是O(V)，而在while循环内部执行的for循环的时间复杂度是O(E)。 那么算法的时间复杂度就是O(VE+E)=O(VE)。 但是，根据我的教科书，它是 O(V+E)。 那我是不是计算错了？

Answer 1

嗯，因为这是最坏的情况，所以你的分析是正确的，但不严格。只要队列中有顶点，while 循环就会运行。只有颜色为白色的顶点才会排队，在这种情况下，它们的颜色会变成灰色，因此它们永远不会再次排队。这告诉您队列可以变得与 V 一样大。

在每次迭代中，您都会迭代顶点的邻接列表，因此总体运行时间是邻接列表长度之和 + V。总和为 O(E)。运行时间为O(V+E)。

记住在无向图中，以下内容成立可能会很有用:所有顶点的度数总和 = 2 * E。要看到这一点，请注意每条边 (x,y) 将被计算两次:一次在 x 的度数中，一次在 y 的度数中。