Algorytmy i struktury danych · Senior · Pytanie 72 z 75
Jaki jest główny powód, by wybrać macierz sąsiedztwa zamiast list sąsiedztwa?
- 1Szybsze przechodzenie po wszystkich sąsiadach
- 2Mniejsze zużycie pamięci na rzadkich grafach
- ✓Poprawna odpowiedź: Sprawdzenie krawędzi w O(1) na gęstych grafach
Wyjaśnienie
Sprawdzenie matrix[u][v] jest natychmiastowe, a dla gęstych grafów pamięć O(V²) nie jest marnowana. Dla rzadkich grafów listy wygrywają pamięcią i przechodzeniem po sąsiadach.