Ta odpowiedź nie dotyczy tylko C ++, ponieważ wszystko, o czym wspomniano, dotyczy samych struktur danych, niezależnie od języka. A moja odpowiedź jest taka, że znasz podstawową strukturę list i macierzy sąsiedztwa.
Pamięć
Jeśli głównym problemem jest pamięć, możesz skorzystać z poniższego wzoru, aby uzyskać prosty wykres, który zezwala na pętle:
Macierz przylegania zajmuje n 2 /8 rozmiar bajtów (jeden bit na pozycji).
Lista sąsiedztwa zajmuje przestrzeń 8e, gdzie e jest liczbą krawędzi (komputer 32-bitowy).
Jeśli zdefiniujemy gęstość wykresu jako d = e / n 2 (liczba krawędzi podzielona przez maksymalną liczbę krawędzi), możemy znaleźć „punkt przerwania”, w którym lista zajmuje więcej pamięci niż macierz:
8e> N 2 /8 , gdy D> 1/64
Tak więc przy tych liczbach (nadal specyficznych dla 32-bitów) punkt przerwania ląduje na 1/64 . Jeśli gęstość (e / n 2 ) jest większa niż 1/64, wtedy matryca jest lepsza, jeśli chcesz zaoszczędzić pamięć.
Możesz przeczytać o tym na Wikipedii (artykuł o macierzach sąsiedztwa) i wielu innych witrynach.
Uwaga dodatkowa : można poprawić wydajność przestrzenną macierzy sąsiedztwa, używając tablicy haszującej, w której klucze są parami wierzchołków (tylko niekierowane).
Iteracja i wyszukiwanie
Listy sąsiedztwa to zwarty sposób przedstawiania tylko istniejących krawędzi. Jednak odbywa się to kosztem możliwie powolnego wyszukiwania określonych krawędzi. Ponieważ każda lista jest tak długa, jak stopień wierzchołka, czas wyszukiwania najgorszego przypadku przy sprawdzaniu określonej krawędzi może wynosić O (n), jeśli lista jest nieuporządkowana. Jednak wyszukiwanie sąsiadów wierzchołka staje się trywialne, a dla rzadkiego lub małego wykresu koszt iteracji przez listy sąsiadów może być znikomy.
Z drugiej strony macierze sąsiedztwa zajmują więcej miejsca, aby zapewnić stały czas wyszukiwania. Ponieważ istnieje każdy możliwy wpis, możesz sprawdzić istnienie krawędzi w stałym czasie za pomocą indeksów. Jednak wyszukiwanie sąsiadów zajmuje O (n), ponieważ musisz sprawdzić wszystkich możliwych sąsiadów. Oczywistą wadą przestrzeni jest to, że w przypadku rzadkich wykresów dodaje się dużo wypełnienia. Zobacz omówienie pamięci powyżej, aby uzyskać więcej informacji na ten temat.
Jeśli nadal nie masz pewności, czego użyć : większość problemów w świecie rzeczywistym tworzy rzadkie i / lub duże wykresy, które lepiej nadają się do reprezentacji list sąsiedztwa. Mogą wydawać się trudniejsze do zaimplementowania, ale zapewniam cię, że tak nie jest, a kiedy piszesz BFS lub DFS i chcesz pobrać wszystkich sąsiadów węzła, dzieli ich tylko jedna linia kodu. Pamiętaj jednak, że ogólnie nie promuję list sąsiedztwa.