Почему сложность BFS O(V+E) вместо O(V*E)?

Question

Какой-то псевдокод здесь (не обращая внимания на мой стиль)

Начиная с v1(в очереди):

function BFS(queue Q)
  v2 = dequeue Q
  enqueue all unvisited connected nodes of v2 into Q
  BFS(Q)
end // maybe minor problems here

Поскольку в графе есть V вершин, и эти V вершины связаны с E ребрами, и посещение подключенных узлов (эквивалентное посещению соединенных ребер) находится во внутреннем цикле (внешний цикл - это сама рекурсия), мне кажется, что сложность должна быть O(V*E), а не O(V+E). Кто-нибудь может объяснить это для меня?

Answer 1

E - это не количество ребер, смежных с каждой вершиной, а фактически общее число ребер в графе. Такое определение полезно, потому что у вас не обязательно одинаковое количество ребер в каждой отдельной вершине.

Поскольку каждое ребро посещается один раз к моменту окончания DFS, вы получаете O(E) сложность из этой части. Затем вы добавляете O(V) для посещения каждой вершины один раз и получаете O(V + E) в сумме.