的基本算法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

所以，我觉得时间复杂度将是：

So I would think the time complexity would be:

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

其中， v 是顶点 1 到 N

首先，是我说的话是否正确？其次，这是怎么 O（N + E），和直觉至于为什么将是非常好的。谢谢

Firstly, is what I've said correct? Secondly, how is this O(N + E), and intuition as to why would be really nice. Thanks

推荐答案

您总和

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

and the first group is O(N) while the other is O(E).