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

129

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?

magiix
źródło
21
Struktura, której używasz, nie zależy od języka, ale od problemu, który próbujesz rozwiązać.
avakar,
1
Miałem na myśli ogólne zastosowanie, takie jak algorytm djikstra, zadałem to pytanie, ponieważ nie wiem, czy implementacja powiązanej listy jest warta wypróbowania, ponieważ jest trudniejsza do zakodowania niż macierz sąsiedztwa.
magiix,
Listy w C ++ są tak proste, jak pisanie std::list(lub jeszcze lepiej std::vector).
avakar,
1
@avakar: lub std::dequelub std::set. Zależy to od tego, jak wykres będzie się zmieniał w czasie i jakie algorytmy zamierzasz na nich uruchomić.
Alexandre C.

Odpowiedzi:

125

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)
Mark Byers
źródło
listy z linkami są trudniejsze do zakodowania, czy uważasz, że warto poświęcić trochę czasu na naukę ich implementacji?
magiix,
11
@magiix: Tak, myślę, że w razie potrzeby powinieneś zrozumieć, jak zakodować połączone listy, ale ważne jest również, aby nie wymyślać koła na nowo: cplusplus.com/reference/stl/list
Mark Byers,
Czy ktoś może podać link z czystym kodem, na przykład do wyszukiwania Breadth w formacie list połączonych?
magiix,
78

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.

klucze
źródło
9
+1 dla wglądu, ale musi to zostać poprawione przez rzeczywistą strukturę danych używaną do przechowywania list sąsiedztwa. Możesz chcieć zapisać dla każdego wierzchołka jego listę przylegania jako mapę lub wektor, w którym to przypadku rzeczywiste liczby w twoich formułach muszą zostać zaktualizowane. Podobne obliczenia można również wykorzystać do oceny progów rentowności dla złożoności czasowej poszczególnych algorytmów.
Alexandre C.
3
Tak, ta formuła dotyczy konkretnego scenariusza. Jeśli chcesz zgrubnej odpowiedzi, użyj tej formuły lub zmodyfikuj ją zgodnie ze swoimi specyfikacjami w razie potrzeby (na przykład większość ludzi ma obecnie komputer 64-bitowy :))
keyser Kwietnia
1
Dla zainteresowanych wzór na punkt załamania (maksymalna liczba średnich krawędzi na wykresie n węzłów) to e = n / s, gdzie sjest rozmiar wskaźnika.
zwolnił
33

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.

wprowadź opis obrazu tutaj

John Red
źródło
W przypadku, gdy nie wiadomo, czy wykres jest gęsty, czy rzadki, czy należałoby powiedzieć, że złożoność przestrzenna dla listy sąsiedztwa wyniosłaby O (v + e)?
W przypadku większości praktycznych algorytmów jedną z najważniejszych operacji jest iteracja po wszystkich krawędziach wychodzących z danego wierzchołka. Możesz dodać go do swojej listy - to O (stopień) dla AL i O (V) dla AM.
maksymalnie
@johnred, czyż nie lepiej jest powiedzieć, że dodanie wierzchołka (czasu) dla AL to O (1), ponieważ zamiast O (en), ponieważ tak naprawdę nie dodajemy krawędzi podczas dodawania wierzchołka. Dodanie krawędzi można potraktować jako oddzielną operację. W przypadku AM ma to sens, ale nawet tam musimy tylko zainicjować odpowiednie wiersze i kolumnę nowego wierzchołka do zera. Dodanie krawędzi nawet dla AM można rozliczyć oddzielnie.
Usman
Jak dodaje się wierzchołek do AL O (V)? Musimy stworzyć nową macierz, skopiować do niej poprzednie wartości. Powinno być O (v ^ 2).
Alex_ban
19

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.

Alex Ntousias
źródło
co, jeśli używasz słowników do przechowywania listy sąsiedztwa, to da ci obecność przewagi w amortyzowanym czasie O (1).
Rohith Yeravothula
10

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

Przykładowy wykres
wprowadź opis obrazu tutaj

Macierz sąsiedztwa: Tworzymy macierz, która ma liczbę wierszy i kolumn n, więc w pamięci zajmie przestrzeń proporcjonalną do n 2 . 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 2 ). (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 2 ))

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

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

Muhammed Kadir
źródło
7

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.

EDYTOWAĆ

To poprzednie pytanie na temat SO prawdopodobnie pomoże:

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

Binary Nerd
źródło
Dziękuję, sprawdzę tę bibliotekę
magiix,
+1 za wykres doładowania. To jest droga (z wyjątkiem oczywiście, jeśli jest to cel edukacyjny)
Tristram Gräbener
5

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.)

Evgeni Sergeev
źródło
2
W przypadku algorytmów takich jak DFS i BFS, jeśli używasz macierzy, to za każdym razem, gdy chcesz znaleźć sąsiednie węzły, musisz sprawdzić cały wiersz, podczas gdy masz już sąsiednie węzły na sąsiedniej liście. Dlaczego myślisz an adjacency list is as good as a matrixw takich przypadkach?
realUser404
@ realUser404 Dokładnie, skanowanie całego wiersza macierzy jest operacją O (n). Listy sąsiedztwa są lepsze dla rzadkich wykresów, kiedy trzeba przejść przez wszystkie wychodzące krawędzie, mogą to zrobić w O (d) (d: stopień węzła). Macierze mają jednak lepszą wydajność pamięci podręcznej niż listy sąsiedztwa, ze względu na dostęp sekwencyjny, więc w przypadku nieco gęstych wykresów skanowanie macierzy może mieć większy sens.
Jochem Kuijpers
3

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).

zwolnił kawior
źródło
Nie rozumiem tej części d = (4 * 300) / (300 * 300), prawda d = 4 / (300 * 300)? Ponieważ formuła to d = e / n^2.
Saurabh
2

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?

ChrisOdney
źródło
1

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).

max
źródło
1

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.

justcoding121
źródło
W przypadku macierzy sąsiedztwa usuń wierzchołek przyjmuje O (V ^ 2) nie O (V)
Saurabh
Tak. Ale jeśli użyjesz słownika do śledzenia indeksów tablic, to zejdzie do O (V). Spójrz na tę implementację RemoveVertex .
justcoding121