Почему сложность BFS O(V+E) вместо O(V*E)?
Какой-то псевдокод здесь (не обращая внимания на мой стиль)
Начиная с 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). Кто-нибудь может объяснить это для меня?
1 ответ
E - это не количество ребер, смежных с каждой вершиной, а фактически общее число ребер в графе. Такое определение полезно, потому что у вас не обязательно одинаковое количество ребер в каждой отдельной вершине.
Поскольку каждое ребро посещается один раз к моменту окончания DFS, вы получаете O(E) сложность из этой части. Затем вы добавляете O(V) для посещения каждой вершины один раз и получаете O(V + E) в сумме.