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

Question

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) 是怎样的，以及关于为什么的直觉会非常好。谢谢

Answer 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)。