小编典典

为什么 DFS 和 BFS 的时间复杂度都是 O( V + E )

all

BFS的基本算法:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

所以我认为时间复杂度是:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

v顶点1在哪里n

首先,我说的对吗?其次,这是怎么回事O(N + E),以及为什么会非常好的直觉。谢谢


阅读 71

收藏
2022-08-16

共1个答案

小编典典

你的总和

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

可以改写为

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

第一组是O(N),而另一组是O(E)

2022-08-16