O algoritmo básico para o 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

Então eu acho que a complexidade do tempo seria:

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

Ondev é vértice1 paran

Em primeiro lugar, o que eu disse é correto? Em segundo lugar, como é issoO(N + E)e intuição de por que seria muito legal. obrigado