算法技术手册（原书第2 版）

140

｜

第

6

章

6.3.4 算法分析

在初始化时，

广度优先搜索

会更新所有顶点的信息，因此初始化的费用是

O

(

V

)

。当第一

次访问一个顶点时（染为灰色），它会被放入队列，并且所有顶点都不会被添加两次。

由于队列能够在常数时间添加或者删除元素，所以维护队列的费用是

O

(

V

)

。最后，每一

个顶点都仅仅会从队列中删除一次，并且它的所有邻接顶点也只会被访问一次，因此，

边循环处理的次数上限为边的总数，即

O

(

E

)

。因此总的性能费用为

O

(

V

+

E

)

。

广度优先搜索小结

最好情况、平均情况和最好情况：

O

(

V

+

E

)

breadthFirstSearch (G, s)

foreach v in V do

pred[v] = -1

dist[v] =

∞

color[v] = White

❶

color[s] = Gray

dist[s] = 0

Q = empty Queue

❷

enqueue (Q, s)

while Q is not empty do

u = head(Q)

foreach neighbor v of u do

if color[v] = White then

dist[v] = dist[u] + 1

pred[v] = u

color[v] = Gray

enqueue (Q, v)

dequeue (Q)

color[u] = Black

❸

end

❶

首先将所有顶点标记为未被访问。 ...