Algorytmy i struktury danych · Junior · Pytanie 57 z 75
Jak zwykle przechowuje się graf z wieloma wierzchołkami, ale niewieloma krawędziami?
- 1Jako macierz n × n wypełnioną zerami i jedynkami
- 2Jako jedną posortowaną tablicę wszystkich wierzchołków
- ✓Poprawna odpowiedź: Jako listę sąsiedztwa: każdy wierzchołek z jego sąsiadami
Wyjaśnienie
Lista sąsiedztwa zajmuje O(V + E) pamięci, a macierz zawsze O(V²), co jest rozrzutne dla grafów rzadkich. Macierz przydaje się dla grafów gęstych albo gdy potrzebny jest test „czy jest krawędź?” w O(1).