Pytanie Co jest lepsze, listy przyległości lub macierze sąsiedztwa dla problemów z wykresem w C ++?


Co jest lepsze, listy przyległości lub macierz sąsiedztwa, problemy z wykresem w C ++? Jakie są zalety i wady każdego z nich?


94
2018-02-07 20:59


pochodzenie


Struktura, której używasz, nie zależy od języka, ale od problemu, który próbujesz rozwiązać. - avakar
Miałem na celu ogólne zastosowanie, takie jak algorytm Djikstry, zadałem to pytanie, ponieważ nie wiem, czy implementacja listy linków jest warta wypróbowania, ponieważ trudniej jest ją kodować niż macierz dopasowania. - magiix
Listy w C ++ są tak proste jak pisanie std::list (Lub jeszcze lepiej, std::vector). - avakar
@avakar: lub std::deque lub std::set. To zależy od sposobu, w jaki wykres zmienia się wraz z upływem czasu i jakie algorytmy zamierzasz na nich uruchomić. - Alexandre C.


Odpowiedzi:


To zależy od problemu.

Macierz sąsiedztwa korzysta z pamięci O (n * n). Ma szybkie wyszukiwanie w celu sprawdzenia obecności lub braku określonej krawędzi, ale powolne do iteracji na wszystkich krawędziach.

Listy rozgraniczeń używają pamięci proporcjonalnie do krawędzi liczb, co może zaoszczędzić dużo pamięci, jeśli macierz sąsiedztwa jest rzadka. Szybko jest iterować po wszystkich krawędziach, ale znalezienie specyficznej krawędzi obecności lub nieobecności jest nieco wolniejsze niż w macierzy.


92
2018-02-07 21:03



powiązane listy są trudniejsze do zakodowania, myślisz, że wdrożenie warto poświęcić trochę czasu na naukę? - magiix
@magiix: Tak, myślę, że powinieneś zrozumieć, jak zakodować powiązane listy, jeśli jest to konieczne, ale ważne jest również, aby nie odkrywać koła na nowo: cplusplus.com/reference/stl/list - Mark Byers
Czy ktoś może podać link z czystym kodem? Najpierw obszerne wyszukiwanie w formacie list połączonych? - magiix
Korzystanie ze std :: list geeksforgeeks.org/breadth-first-traversal-for-a-graph - atif93


Ta odpowiedź nie dotyczy tylko języka C ++, ponieważ wszystkie wymienione informacje dotyczą samych struktur danych, niezależnie od języka. Moja odpowiedź zakłada, że ​​znasz podstawową strukturę list i macierzy sąsiedztwa.

Pamięć

Jeśli pamięcią jest twoja główna uwaga, możesz zastosować tę formułę dla prostego wykresu, który pozwala na pętle:

Macierz sąsiedztwa zajmuje n2/ 8 bajtów (jeden bit na wpis).

Lista przyległa zajmuje przestrzeń 8e, gdzie e to liczba krawędzi (komputer 32-bitowy).

Jeśli zdefiniujemy gęstość wykresu jako d = e / n2   (liczba krawędzi podzielona przez maksymalną liczbę krawędzi), możemy znaleźć "punkt przerwania", gdzie lista zajmuje więcej pamięci niż macierz:

8e> n2/ 8   gdy d> 1/64

Tak więc przy tych liczbach (nadal 32-bitowych) punkt przerwania trafia na 1/64.  Jeśli gęstość (e / n2) jest większy niż 1/64, a następnie a matryca jest preferowane, jeśli chcesz zaoszczędzić pamięć.

Możesz o tym przeczytać na stronie wikipedia (artykuł na temat macierzy sąsiedztwa) i wiele innych stron.

Dygresja: Można poprawić efektywność przestrzenną macierzy sąsiedztwa za pomocą tabeli mieszania, w której klucze są parami wierzchołków (tylko nieokreślone).

Iteracja i wyszukiwanie

Listy rozgraniczeń są zwartym sposobem reprezentowania tylko istniejących krawędzi. Jednak dzieje się to kosztem powolnego wyszukiwania określonych krawędzi. Ponieważ każda lista jest tak długa, jak stopień wierzchołka, czas wyszukiwania najgorszego przypadku sprawdzenia dla konkretnej krawędzi może być O (n), jeśli lista jest nieuporządkowana. Jednak szukanie sąsiadów wierzchołka staje się trywialne, a na niewielki lub za mały wykres koszt iteracji przez listy przyległości może być nieistotny.

Macierze sąsiadujące z drugiej strony wykorzystują 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 paddingu. 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 generuje rozrzedzone i / lub duże wykresy, które lepiej pasują do reprezentacji listy przyległych. Mogą wydawać się trudniejsze do wdrożenia, ale zapewniam cię, że tak nie jest, a kiedy piszesz BFS lub DFS i chcesz pobrać wszystkich sąsiadów węzła, są one tylko jedną linią kodu. Pamiętaj jednak, że ogólnie nie promuję list rozgłoszeniowych.


67
2018-03-24 13:27



+1 dla wglądu, ale musi to być poprawione przez faktyczną strukturę danych używaną do przechowywania list sąsiednich. Możesz chcieć zapisać dla każdego wierzchołka swoją listę sąsiedztwa jako mapę lub wektor, w którym to przypadku aktualne liczby w twoich formułach muszą zostać zaktualizowane. Podobne obliczenia można wykorzystać do oceny progu rentowności dla złożoności czasowej poszczególnych algorytmów. - Alexandre C.
Tak, ta formuła dotyczy konkretnego scenariusza. Jeśli chcesz uzyskać zgrubną odpowiedź, zastosuj tę formułę lub zmodyfikuj ją zgodnie ze swoimi wymaganiami (na przykład większość ludzi ma obecnie komputer 64-bitowy :)) - keyser
Dla zainteresowanych, formuła punktu przerwania (maksymalna liczba średnich krawędzi na wykresie n węzłów) jest e = n / s, gdzie s jest wielkości wskaźnika. - dcousens


Okej, skompilowałem złożoność czasową i przestrzenną podstawowych operacji na wykresach.
Poniższy obrazek powinien być zrozumiały.
Zwróć uwagę, że macierz sąsiedztwa jest lepsza, gdy oczekujemy, że wykres będzie gęsty, a także, że lista współrzędnych jest preferowana, gdy spodziewamy się, że wykres będzie rzadki.
Podjąłem pewne założenia. Zapytaj mnie, czy złożoność (czas lub przestrzeń) wymaga wyjaśnienia. (Na przykład, dla rozrzedzonego wykresu, wziąłem En za małą stałą, ponieważ założyłem, że dodanie nowego wierzchołka doda tylko kilka krawędzi, ponieważ spodziewamy się, że wykres pozostanie nieliczny nawet po dodaniu tego wierzchołek.)

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

enter image description here


28
2017-07-18 07:51



Jeśli nie wiadomo, czy wykres jest gęsty czy rzadki, czy słusznie byłoby powiedzieć, że złożoność przestrzeni dla listy przyległości to O (v + e)? - sidgupta234
Tak, byłoby dobrze. - John Red
Dla większości praktycznych algorytmów jedną z najważniejszych operacji jest iteracja przez wszystkie krawędzie wychodzące z danego wierzchołka. Możesz dodać go do swojej listy - to O (stopień) dla AL i O (V) dla AM. - max
@johnred nie jest lepiej powiedzieć, że Dodawanie wierzchołka (czasu) dla AL to O (1), ponieważ zamiast O (en), ponieważ tak naprawdę nie dodajemy krawędzi przy dodawaniu wierzchołka. Dodawanie krawędzi można traktować jako oddzielną operację. Dla AM sensowne jest rozliczenie, ale nawet tam wystarczy zainicjować odpowiednie wiersze i kolumny nowego wierzchołka na zero. Dodanie krawędzi nawet dla AM można uwzględnić oddzielnie. - Undefined
Jak dodaje się wierzchołek do AL O (V)? Musimy stworzyć nową macierz, skopiować do niej poprzednie wartości. Powinien to być O (v ^ 2). - Alex_ban


To zależy od tego, czego szukasz.

Z matryce przyległości możesz szybko odpowiedzieć 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. The minusem jest to, że musisz używać nadmiernej przestrzeni, szczególnie w przypadku wykresów z wieloma wierzchołkami, co jest bardzo nieefektywne, szczególnie jeśli Twój wykres jest rzadki.

Z drugiej strony, z listy przyległości trudniej jest sprawdzić, czy dana krawędź znajduje się na wykresie, ponieważ musisz przeszukać odpowiednią listę, aby znaleźć krawędź, ale są one bardziej efektywne pod względem przestrzeni.

Generalnie jednak listy przyległości są właściwą strukturą danych dla większości aplikacji wykresów.


16
2018-02-07 21:04





Jeśli szukasz analizy grafów w C ++, prawdopodobnie pierwszym miejscem do rozpoczęcia będzie zwiększyć bibliotekę wykresów, która implementuje wiele algorytmów, w tym BFS.

EDYTOWAĆ

To poprzednie pytanie na temat SO prawdopodobnie pomoże:

jak utworzyć-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search


8
2018-02-07 23:36



Dzięki temu sprawdzę tę bibliotekę - magiix
+1 dla wykresu zwiększenia. To jest droga (z wyjątkiem oczywiście, jeśli jest to do celów edukacyjnych) - Tristram Gräbener


Najlepiej odpowiedzieć na to przykładem.

Myśleć o Floyd-Warshall na przykład. Musimy użyć macierzy sąsiedztwa lub algorytm będzie asymptotycznie wolniejszy.

A co jeśli jest to gęsty wykres na 30 000 wierzchołków? Wtedy matryca przyległości może mieć sens, ponieważ będziesz przechowywać 1 bit na parę wierzchołków, zamiast 16 bitów na krawędź (minimum, które potrzebujesz na liście przyległości): to 107 MB zamiast 1,7 GB.

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


4
2017-11-25 11:04





Aby dodać do odpowiedzi keyser5053 na temat użycia pamięci.

Dla każdego skierowanego wykresu zużywa się macierz sąsiedztwa (przy 1 bitach na krawędź) n^2 * (1) bity pamięci.

Dla kompletny wykres, lista sąsiednich (z wskaźnikami 64-bitowymi) jest zużywana n * (n * 64) bity pamięci, z wyłączeniem narzutów listy.

Dla niekompletnego wykresu zużywa się lista przyległości 0 bity pamięci, z wyłączeniem narzutów listy.


W przypadku listy przyległości możesz użyć następującej formuły, aby określić maksymalną liczbę krawędzi (e) zanim macierz sąsiedztwa będzie optymalna dla pamięci.

edges = n^2 / s określić maksymalną liczbę krawędzi, gdzie s jest wskaźnikiem rozmiaru platformy.

Jeśli wykres jest dynamicznie aktualizowany, można utrzymać tę wydajność przy średniej liczbie krawędzi (na węzeł) n / s.


Niektóre przykłady (z wskaźnikami 64-bitowymi).

Dla skierowanego wykresu, gdzie n wynosi 300, optymalna liczba krawędzi na węzeł przy użyciu listy przyległości to:

= 300 / 64
= 4

Jeśli podłączymy to do formuły keyser5053, d = e / n^2 (gdzie e to całkowita liczba krawędzi), widzimy, ż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 dla wskaźnika mogą być przesadne. Jeśli zamiast tego stosujesz 16-bitowe liczby całkowite jako przesunięcia wskaźnika, możemy zmieścić do 18 krawędzi przed punktem przełamania.

= 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 z list sąsiednich (64*2 dla wektora i wskaźników 64-bitowych).


3
2018-01-23 08:59





W zależności od implementacji macierzy Adjacency, "n" wykresu powinno być wcześniej znane ze skutecznej implementacji. Jeśli wykres jest zbyt dynamiczny i wymaga od czasu do czasu rozbudowy matrycy, to można to również uznać za wadę?


2
2018-05-08 08:36





Jeśli użyjesz tabeli mieszania zamiast macierzy lub listy sąsiedztwa, uzyskasz lepsze lub takie same duże czasy uruchamiania i przestrzeń dla wszystkich operacji (sprawdzanie krawędzi jest O(1), uzyskanie wszystkich sąsiednich krawędzi O(degree)itp.).

Istnieje pewien stały napływ czynnika, zarówno w czasie wykonywania, jak i w przestrzeni (tablica haszująca nie jest tak szybka jak lista połączona lub wyszukiwanie tablicy, a zajmuje przyzwoitą ilość dodatkowego miejsca w celu zmniejszenia kolizji).


2
2017-11-24 18:11