广度优先搜索的执行时间

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

不，该算法确实是 O(VE)，但也是 O(V + E)。您的界限很松散，因为在扫描邻接列表时每条边最多被考虑两次。

Answer 2

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

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

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

广度优先搜索的执行时间

Execution time of Breadth-first search

algorithm

time

breadth-first-search