Złożoność czasowa i pamięciowa
Lekcja 7 z 9 w kursie Przeszukiwanie w głąb — algorytmy grafowe w Coddy.
Złożoność czasowa:
- O(V + E)
- Tworzenie listy sąsiedztwa obejmuje każdą krawędź raz, a podczas przechodzenia odwiedza się każdy wierzchołek i sprawdza każdą krawędź stałą liczbę razy.
Złożoność pamięciowa:
- O(V + E)
- Lista sąsiedztwa przechowuje każdą krawędź, a tablica odwiedzonych wierzchołków i stos mogą pomieścić po V wierzchołków.
Podsumowanie:
- DFS najpierw eksploruje graf w głąb, cofając się, gdy zabraknie nieodwiedzonych sąsiadów.
- Działa w czasie liniowym i stanowi podstawę wielu algorytmów grafowych.
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 w głąb — 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