Graf mam zaprezentowany w postaci listy sąsiedztwa wierzchołków. Jak mam przetrzymywać wagi poszczególnych krawędzi, aby nie stracić plusów jakie daje ta reprezentacja? (głównie chodzi o pamięć).
Wiadomo, że najprościej jest w macierzy sąsiędztwa, wtedy mamy definicje i wagi krawędzi w jednym, no ale to zajmuje n^2 pamięci..
0
0
Zasadniczo pesymistycznie lista sąsiedztwa też ma O(n2) pamięci. Poza tym pesymistycznie masz n2 wartości do przechowania i zapewniam cie ze nie ma cudów żebyś to przechował w mniejszej ilości pamięci.
Listę sąsiedztwa stosuje się ze względu na pewne ułatwienia jakie przy niektórych algorytmach daje ta reprezentacja. Raczej nie po to żeby oszczędzać pamięć.