Основной алгоритм для 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)и интуиция относительно того, почему это было бы действительно хорошо. Спасибо