Złożoność czasowa i pamięciowa
Lekcja 7 z 9 w kursie Przeszukiwanie wszerz — algorytmy grafowe w Coddy.
Złożoność czasowa:
- O(V + E)
- Każdy wierzchołek jest dodawany do kolejki i usuwany z niej raz, a każda krawędź jest sprawdzana stałą liczbę razy.
Złożoność pamięciowa:
- O(V + E)
- Lista sąsiedztwa przechowuje każdą krawędź, a kolejka i tablica odwiedzonych przechowują do V wierzchołków.
Podsumowanie:
- BFS przeszukuje graf warstwami, używając kolejki i odwiedzając bliższe wierzchołki przed dalszymi.
- Taka kolejność warstw sprawia, że BFS jest podstawowym algorytmem do znajdowania najkrótszych ścieżek w grafach nieważonych.
Spróbuj swoich sił
Ta lekcja nie zawiera wyzwania z kodem.
Sprawdź sięTa lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.
Wszystkie lekcje w sekcji Przeszukiwanie wszerz — algorytmy grafowe
2Algorytm
Jak to działa?PseudokodImplementacja (część 1)Implementacja (część 2)
Złożoność czasowa i pamięciowaPoćwicz samodzielnie: Kompilator C online