Худший случай времени работы BFS

Question

Я путаюсь с сложностью BFS. Википедия говорит: «Сложность времени может быть выражена как O (| V | + | E |), так как каждая вершина и каждое ребро будут изучены в худшем случае».

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 

Для меня худший случай: каждая вершина связана со всеми вершинами Таким образом, цикл, пока будет сделан V раза и в течение времени цикла Е. Худший сценарий 0 (VE).

Что я сделал не так?

Answer 1

Сложность времени BFS равна O (| V | + | E |). V - количество полной вершины, а E - число общего ребра. Вы можете ошибочно принять за E. E не соседние ребра вершины u.

Мы можем реализовать это, как показано ниже.

для каждой функции и в вершинах

для каждых е в соседе (и)

do something. 

Answer 2

Целью BFS является посетить все узлы один раз. Никакая вершина никогда не попадает в очередь во второй раз (что объясняет | V |). | E | суммирования исходит из предположения, что проверка краев инцидентов ничего не стоит по сравнению с посещением. Итак, да, для полного графа (все вершины связаны со всеми другими вершинами) будут проверены края VE ... но проверка их не стоит посещения.