Co jest lepsze, listy sąsiedztwa lub macierze sąsiedztwa dla problemów z grafami w C ++?

Co jest lepsze, listy sąsiedztwa lub macierze sąsiedztwa, dla problemów z grafami w C ++? Jakie są zalety i wady każdego z nich?

To zależy od problemu.

Macierz sąsiedztwa

• Używa pamięci O (n ^ 2)
• Szybkie wyszukiwanie i sprawdzanie obecności lub braku określonej krawędzi
  między dowolnymi dwoma węzłami O (1)
• Powolne jest iterowanie po wszystkich krawędziach
• Dodawanie / usuwanie węzła jest powolne; złożona operacja O (n ^ 2)
• Dodanie nowej krawędzi jest szybkie O (1)

Lista sąsiedztwa

• Wykorzystanie pamięci zależy od liczby krawędzi (nie liczby węzłów),
  co może zaoszczędzić dużo pamięci, jeśli macierz sąsiedztwa jest rzadka
• Znalezienie obecności lub braku określonej krawędzi między dowolnymi dwoma węzłami
  jest nieco wolniejsze niż w przypadku macierzy O (k); gdzie k jest liczbą węzłów sąsiadów
• Iteracja po wszystkich krawędziach jest szybka, ponieważ można uzyskać bezpośredni dostęp do wszystkich sąsiadów węzła
• Dodanie / usunięcie węzła jest szybkie; łatwiejsze niż reprezentacja macierzowa
• Dodanie nowej krawędzi jest szybkie O (1)

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 ² /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 ² (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 ² /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 ² ) 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.

OK, skompilowałem złożoność czasu i przestrzeni podstawowych operacji na wykresach.
Poniższy obraz powinien być oczywisty.
Zwróć uwagę, że macierz przylegania jest lepsza, gdy spodziewamy się, że wykres będzie gęsty, a lista przyległości jest lepsza, gdy spodziewamy się, że wykres będzie rzadki.
Zrobiłem kilka założeń. Zapytaj mnie, czy złożoność (czas lub przestrzeń) wymaga wyjaśnienia. (Na przykład w przypadku rzadkiego wykresu przyjęłem En jako małą stałą, ponieważ założyłem, że dodanie nowego wierzchołka doda tylko kilka krawędzi, ponieważ spodziewamy się, że wykres pozostanie rzadki nawet po dodaniu tego wierzchołek.)

Proszę, powiedz mi, czy są jakieś błędy.

To zależy od tego, czego szukasz.

Dzięki macierzom sąsiedztwa możesz szybko odpowiadać na pytania dotyczące tego, czy konkretna krawędź między dwoma wierzchołkami należy do wykresu, a także możesz szybko wstawiać i usuwać krawędzie. Minusem jest to, że trzeba używać nadmiernej miejsca, zwłaszcza dla wykresów z wielu wierzchołków, co jest bardzo nieefektywne zwłaszcza jeśli wykres jest rzadki.

Z drugiej strony, przy listach sąsiedztwa trudniej jest sprawdzić, czy dana krawędź jest na wykresie, ponieważ trzeba przeszukać odpowiednią listę, aby znaleźć krawędź, ale są one bardziej wydajne przestrzennie.

Jednak generalnie listy sąsiedztwa są właściwą strukturą danych dla większości zastosowań wykresów.

Załóżmy, że mamy graf, który ma n liczbę węzłów i m liczbę krawędzi,

Przykładowy wykres

Macierz sąsiedztwa: Tworzymy macierz, która ma liczbę wierszy i kolumn n, więc w pamięci zajmie przestrzeń proporcjonalną do n ² . Sprawdzenie, czy dwa węzły nazwanych U i V jest krawędź między nimi zajmie Θ (1) Czas. Na przykład sprawdzenie, czy (1, 2) jest krawędzią, w kodzie będzie wyglądać następująco:

if(matrix[1][2] == 1)

Jeśli chcesz zidentyfikować wszystkie krawędzie, musisz iterować po macierzy, co będzie wymagało dwóch zagnieżdżonych pętli i zajmie Θ (n ² ). (Możesz po prostu użyć górnej trójkątnej części macierzy, aby określić wszystkie krawędzie, ale znowu będzie Θ (n ² ))

Lista sąsiedztwa: Tworzymy listę, którą każdy węzeł wskazuje również na inną listę. Twoja lista będzie miała n elementów, a każdy element będzie wskazywał na listę, która ma liczbę elementów równą liczbie sąsiadów tego węzła (spójrz na obrazek dla lepszej wizualizacji). Więc zajmie przestrzeń w pamięci, która jest proporcjonalna do n + m . Sprawdzenie, czy (u, v) jest krawędzią, zajmie O (deg (u)) czasu, w którym deg (u) równa się liczbie sąsiadów u. Ponieważ co najwyżej musisz iterować po liście wskazywanej przez u. Zidentyfikowanie wszystkich krawędzi zajmie Θ (n + m).

Lista sąsiedztwa przykładowego wykresu

Powinieneś dokonać wyboru zgodnie ze swoimi potrzebami. Z powodu mojej reputacji nie mogłem umieścić zdjęcia matrycy, przepraszam za to

Jeśli patrzysz na analizę grafów w C ++, prawdopodobnie pierwszym miejscem do rozpoczęcia byłaby biblioteka grafów doładowania , która implementuje szereg algorytmów, w tym BFS.

• Zwiększ dokumentację biblioteki wykresów

EDYTOWAĆ

To poprzednie pytanie na temat SO prawdopodobnie pomoże:

jak-stworzyc-podkreslenie-ac-nieukierunkowanego-wykres-i-przechodzenie-w-dogłębne-pierwsze-przeszukanie h

Najlepiej odpowiedzieć na to przykłady.

Pomyśl na przykład o Floyd-Warshall . Musimy użyć macierzy sąsiedztwa, inaczej algorytm będzie asymptotycznie wolniejszy.

A co, jeśli jest to gęsty wykres na 30 000 wierzchołkach? Wtedy macierz sąsiedztwa może mieć sens, ponieważ będziesz przechowywać 1 bit na parę wierzchołków, a nie 16 bitów na krawędź (minimum, którego potrzebujesz do listy sąsiedztwa): to 107 MB, a nie 1,7 GB.

Ale w przypadku algorytmów, takich jak DFS, BFS (i tych, które go używają, jak Edmonds-Karp), wyszukiwanie priorytetowe (Dijkstra, Prim, A *) itp., Lista sąsiedztwa jest równie dobra jak macierz. Cóż, macierz może mieć niewielką krawędź, gdy wykres jest gęsty, ale tylko przez niezauważalny stały współczynnik. (Ile? To kwestia eksperymentowania.)

Aby dodać do keyser5053 odpowiedź dotyczącą użycia pamięci.

W przypadku dowolnego ukierunkowanego wykresu macierz sąsiedztwa (przy 1 bicie na krawędź) zużywa n^2 * (1)bity pamięci.

Aby uzyskać pełny wykres , lista przylegania (z 64-bitowymi wskaźnikami) zużywa n * (n * 64)bity pamięci, z wyłączeniem narzutu listy.

W przypadku niekompletnego wykresu lista sąsiedztwa zużywa 0bity pamięci, z wyłączeniem narzutu listy.

W przypadku listy przylegania można użyć następującego wzoru, aby określić maksymalną liczbę krawędzi ( e), zanim macierz sąsiedztwa będzie optymalna dla pamięci.

edges = n^2 / sdo określenia maksymalnej liczby krawędzi, gdzie sjest rozmiar wskaźnika platformy.

Jeśli wykres aktualizuje się dynamicznie, możesz utrzymać tę wydajność przy średniej liczbie krawędzi (na węzeł) wynoszącej n / s.

Kilka przykładów z 64-bitowymi wskaźnikami i dynamicznym wykresem (dynamiczny wykres skutecznie aktualizuje rozwiązanie problemu po zmianach, zamiast obliczać je od nowa za każdym razem po dokonaniu zmiany).

Dla grafu skierowanego, gdzie nwynosi 300, optymalna liczba krawędzi na węzeł przy użyciu listy przylegania to:

= 300 / 64
= 4

Jeśli podłączymy to do wzoru keyser5053 d = e / n^2(gdzie ejest całkowita liczba krawędzi), zobaczymy, że jesteśmy poniżej punktu przerwania ( 1 / s):

d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156

Jednak 64 bity wskaźnika mogą być przesadzone. Jeśli zamiast tego użyjesz 16-bitowych liczb całkowitych jako przesunięć wskaźnika, możemy dopasować do 18 krawędzi przed punktem przerwania.

= 300 / 16
= 18

d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625

Każdy z tych przykładów ignoruje narzut samych list przylegania ( 64*2dla wektorów i wskaźników 64-bitowych).

W zależności od implementacji macierzy przylegania, „n” wykresu powinno być znane wcześniej, aby zapewnić wydajną implementację. Jeśli wykres jest zbyt dynamiczny i wymaga od czasu do czasu rozszerzania macierzy, można to również zaliczyć do wad?

Jeśli użyjesz tablicy haszującej zamiast macierzy przylegania lub listy, uzyskasz lepszy lub taki sam czas wykonywania i przestrzeń dla dużych O dla wszystkich operacji (sprawdzanie krawędzi to O(1), pobieranie wszystkich sąsiednich krawędzi O(degree)itp.).

Istnieje jednak pewien stały narzut czynnikowy zarówno w czasie wykonywania, jak i przestrzeni (tabela skrótów nie jest tak szybka jak połączona lista lub wyszukiwanie w tablicy i zajmuje przyzwoitą ilość dodatkowej przestrzeni, aby zmniejszyć kolizje).

Chciałbym tylko poruszyć kwestię przezwyciężenia kompromisu polegającego na regularnym przedstawianiu listy sąsiedztwa, ponieważ inne odpowiedzi dotyczyły innych aspektów.

Możliwe jest przedstawienie wykresu na liście sąsiedztwa za pomocą zapytania EdgeExists w zamortyzowanym stałym czasie, wykorzystując struktury danych Dictionary i HashSet . Chodzi o to, aby zachować wierzchołki w słowniku i dla każdego wierzchołka trzymamy zestaw skrótów odnoszący się do innych wierzchołków, z którymi ma krawędzie.

Jednym drobnym kompromisem w tej implementacji jest to, że będzie miała złożoność przestrzeni O (V + 2E) zamiast O (V + E), jak na zwykłej liście przylegania, ponieważ krawędzie są tutaj reprezentowane dwukrotnie (ponieważ każdy wierzchołek ma swój własny zestaw skrótów krawędzi). Ale operacje takie jak AddVertex , AddEdge , RemoveEdge mogą być wykonywane w zamortyzowanym czasie O (1) z tą implementacją, z wyjątkiem RemoveVertex, który przyjmuje O (V) jak macierz sąsiedztwa. Oznaczałoby to, że poza prostotą implementacji, macierz sąsiedztwa nie ma żadnej szczególnej korzyści. Możemy zaoszczędzić miejsce na rzadkim wykresie z prawie taką samą wydajnością w tej implementacji listy sąsiedztwa.

Spójrz na poniższe implementacje w repozytorium Github C #, aby uzyskać szczegółowe informacje. Zauważ, że dla wykresu ważonego używa zagnieżdżonego słownika zamiast kombinacji słownik-zestaw skrótów, aby dostosować wartość wagi. Podobnie w przypadku wykresu skierowanego istnieją oddzielne zestawy skrótów dla krawędzi wejściowych i wyjściowych.

Zaawansowane algorytmy

Uwaga: Uważam, że używając leniwego usuwania możemy dalej zoptymalizować operację RemoveVertex do amortyzacji O (1), mimo że nie testowałem tego pomysłu. Na przykład po usunięciu po prostu zaznacz wierzchołek jako usunięty w słowniku, a następnie leniwie wyczyść osierocone krawędzie podczas innych operacji.