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

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

最佳答案

你的钱

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