Podstawowy algorytm dla 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
Więc myślę, że złożoność czasowa byłaby następująca:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
gdzie v
jest wierzchołek 1
nan
Po pierwsze, czy to, co powiedziałem, jest prawidłowe? Po drugie, jak to jest O(N + E)
i intuicja, dlaczego byłoby naprawdę fajnie. Dzięki
DFS (analiza):
O(1)
czasuO(n + m)
czasie, pod warunkiem, że wykres jest reprezentowany przez strukturę listy sąsiedztwaΣv deg(v) = 2m
BFS (analiza):
Li
O(n + m)
czasie pod warunkiem, że wykres jest reprezentowany przez strukturę listy sąsiedztwaΣv deg(v) = 2m
źródło
Bardzo uproszczone bez większych formalności: każda krawędź jest rozpatrywana dokładnie dwa razy, a każdy węzeł jest przetwarzany dokładnie raz, więc złożoność musi być stałą wielokrotnością liczby krawędzi i liczby wierzchołków.
źródło
Złożoność czasowa jest
O(E+V)
zamiast tego,O(2E+V)
ponieważ jeśli złożoność czasowa wynosi n ^ 2 + 2n + 7, to jest zapisywana jako O (n ^ 2).Stąd O (2E + V) jest zapisane jako O (E + V)
ponieważ różnica między n ^ 2 a n ma znaczenie, ale nie ma znaczenia między n a 2n.
źródło
Intuicyjnym wyjaśnieniem tego jest po prostu analiza pojedynczej pętli:
Zatem całkowity czas dla pojedynczej pętli wynosi O (1) + O (e). Teraz zsumuj to dla każdego wierzchołka, ponieważ każdy wierzchołek jest odwiedzany raz. To daje
źródło
Myślę, że każda krawędź była rozważana dwukrotnie i każdy węzeł był odwiedzany raz, więc całkowita złożoność czasowa powinna wynosić O (2E + V).
źródło
Krótkie, ale proste wyjaśnienie:
źródło
Jest to O (V + E), ponieważ każda wizyta w v z V musi odwiedzić każde e z E, gdzie | e | <= V-1. Ponieważ jest V wizyt na v z V, to jest to O (V). Teraz musisz dodać V * | e | = E => O (E). Zatem całkowita złożoność czasowa wynosi O (V + E).
źródło