Algorytmy i struktury danych · Middle · Pytanie 60 z 75
Jaka jest złożoność BFS lub DFS na grafie zapisanym listami sąsiedztwa?
- 1O(V × E)
- ✓Poprawna odpowiedź: O(V + E)
- 3O(V²) w każdym przypadku
Wyjaśnienie
Każdy wierzchołek jest przetwarzany raz, a każda krawędź oglądana raz (dwa razy w grafach nieskierowanych). Z macierzą sąsiedztwa to samo przejście kosztuje O(V²), bo każdy wiersz ma V komórek.