Kiedy listy lub macierze sąsiedztwa są lepszym wyborem?

Powiedziano mi, że użyjemy listy, jeśli wykres jest rzadki, a macierzy, jeśli wykres jest gęsty . Dla mnie to tylko surowa definicja. Nie widzę wiele poza tym. Czy możesz wyjaśnić, kiedy byłby to naturalny wybór?

Z góry dziękuję!

graphs data-structures lists adjacency-matrix użytkownik21312
źródło

Powiązane: stackoverflow.com/a/2218331/5746050 i stackoverflow.com/a/5419933/5746050

Ryan

To nie jest definicja, głównie dlatego, że nie ma jednej definicji „rzadkich” i „gęstych”. Istnieją również inne uwagi, np. Do których aspektów wykresu można uzyskać dostęp, jak często.

Raphael

@Raphael Czy możesz uzyskać więcej informacji na temat innych rozważań?

user21312,

@ user21312, dużą różnicą jest iteracyjność vs dostęp do krawędzi. Jeśli często trzeba wykonywać iteracje po krawędziach, lista przylegania może być bardziej przydatna. Jeśli często musisz ustalić, czy krawędź istnieje lub uzyskać dostęp do jej ciężaru (lub innych informacji), macierz może być lepsza.

ryan

W twoim przypadku prawdopodobnie moglibyśmy nieostrożnie myśleć o definicji „rzadkich” i „gęstych”. Po prostu modeluj złożoność czasową operacji macierzy, której chcesz użyć dla każdego typu struktury danych, i zobacz, gdzie jest „punkt przerwania gęstości”. Myślę, że drugi link @ryan próbuje zrobić coś podobnego

Apiwat Chantawibul

Odpowiedzi:

Przede wszystkim zauważ, że rzadki oznacza, że masz bardzo mało krawędzi, a gęsty oznacza wiele krawędzi lub prawie pełny wykres. Na pełnym wykresie masz krawędzi, gdzie jest liczbą węzłów. $n(n-1)/2$ $n$

Teraz, gdy używamy reprezentacji macierzowej, alokujemy macierzy do przechowywania informacji o połączeniach węzłów, np. jeśli istnieje krawędź między węzłami i , w przeciwnym razie . Ale jeśli użyjemy listy przyległości, mamy tablicę węzłów i każdy węzeł wskazuje na swoją listę przyległości zawierającą TYLKO sąsiednie węzły . $n\times n$ $M[i][j] = 1$ $i$ $j$ $M[i][j] = 0$

Teraz, jeśli wykres jest rzadki i korzystamy z reprezentacji macierzy, wówczas większość komórek macierzy pozostaje nieużywana, co prowadzi do marnowania pamięci. Dlatego zwykle nie używamy reprezentacji macierzowej dla rzadkich wykresów. Wolimy listę sąsiadów.

Ale jeśli wykres jest gęsty, liczba krawędzi jest zbliżona do (pełnego) lub do jeśli wykres jest skierowany za pomocą pętli własnych. Wówczas nie ma przewagi, aby używać listy sąsiedztwa nad macierzą. $n(n-1)/2$ $n^2$

Pod względem złożoności przestrzeni
Macierz adiakencji: Lista adjacencji: gdzie jest liczbą węzłów, jest liczbą krawędzi. $O(n^2)$
$O(n + m)$
$n$ $m$

Gdy wykres jest drzewem bezkierunkowym, wówczas
macierz adiakencji: Lista adjacencji: to (lepiej niż ) $O(n^2)$
$O(n + n)$ $O(n)$ $n^2$

Gdy wykres jest skierowany, kompletny, z pętlami własnymi, to
macierz adiakencji: Lista adjacencji: to (bez różnicy) $O(n^2)$
$O(n + n^2)$ $O(n^2)$

I na koniec, kiedy implementujesz za pomocą macierzy, sprawdzenie, czy istnieje krawędź między dwoma węzłami, zajmuje razy, natomiast w przypadku listy przyległości może zająć czas liniowy w . $O(1)$ $n$

fade2black
źródło

„chociaż lista przylegania może zająć trochę czasu” - biorąc pod uwagę, że lista przylegania (prawdopodobnie) nie ma żadnego naturalnego porządku, dlaczego jest to lista zamiast zestawu skrótów?

Kevin

@Kevin Wtedy nazwano by to „hash sąsiedztwa” zamiast „list”. Możliwe też, dlaczego nie? Ale jeśli po prostu wykonujesz DFS lub BFS lub jakąś inną procedurę, która skanuje systematycznie wszystkie węzły, to jaka jest zaleta używania skrótu nad listą? W każdym razie sprawdziłbyś wszystkie sąsiednie węzły.

fade2black

Dodałbym, że w przypadku nieważonego, niekierowanego przypadku, dla prawie pełnego wykresu bardziej prawdopodobne może być przechowywanie jego dopełnienia, tj. Rzadkiego wykresu. Tak więc matryca jest przydatna, gdy obecna jest w przybliżeniu połowa krawędzi.

M. Winter

Aby odpowiedzieć, podając prostą analogię. Gdybyś musiał przechowywać 6 uncji wody, czy (ogólnie rzecz biorąc) zrobiłbyś to z pojemnikiem o pojemności 5 galonów lub kubkiem o pojemności 8 uncji?

Wracając do pytania… Jeśli większość macierzy jest pusta, to po co z niej korzystać? Zamiast tego wystarczy wymienić każdą wartość. Jeśli jednak twoja lista jest naprawdę długa, dlaczego nie użyć matrycy, aby ją skondensować?

W tym przypadku uzasadnienie listy vs macierzy jest naprawdę takie proste.

PS lista to tak naprawdę tylko macierz jednokolumnowa !!! (próbuje pokazać, jak arbitralna jest decyzja / scenariusz)

źródło

Rozważ wykres z węzłami i krawędziamiIgnorując warunki niskiego rzędu, matryca bitowa dla wykresu używa bitów bez względu na liczbę krawędzi. $N$ $E$ $N^2$

Ile bitów tak naprawdę potrzebujesz?

Zakładając, że krawędzie są niezależne, liczba wykresów z węzłami i krawędziami wynosi . Minimalna liczba bitów wymagana do przechowywania tego podzbioru wynosi . $N$ $E$ ${N^2 \choose E}$ $\log_2 {N^2 \choose E}$

Przyjmiemy bez utraty ogólności, że , to znaczy, że połowa lub mniej krawędzi jest obecnych. Jeśli tak nie jest, możemy zamiast tego zapisać zestaw „bez krawędzi”. $E \le \frac{N^2}{2}$

Jeśli , , więc reprezentacja macierzy jest asymptotycznie optymalna. Jeśli , stosując przybliżenie Stirlinga i trochę arytmetyki, znajdziemy: $E = \frac{N^2}{2}$ $\log_2{N^2 \choose E} = N^2 + o(N^2)$ $E \ll N^2$

\log_{2} (\binom{N^{2}}{E})

$\log_2 {N^2 \choose E}$

= \log_{2} \frac{(N^{2})!}{E! (N^{2} - E)!}

$= \log_2 \frac {(N^2)!} {E! (N^2 - E)!}$

= 2 E \log_{2} N + O (low order terms)

$= 2E \log_2 N + O(\hbox{low order terms})$

Jeśli weźmiesz pod uwagę, że jest rozmiarem liczby całkowitej, która może reprezentować indeks węzła, optymalną reprezentacją jest tablica identyfikatorów węzłów , czyli tablica par indeksów węzłów. $\log_2 N$ $2E$

To powiedziawszy, dobrą miarą rzadkości jest entropia, która jest również liczbą bitów na krawędź optymalnej reprezentacji. Jeśli jest prawdopodobieństwem obecności krawędzi, entropia to . Dla entropia wynosi 2 (tj. Dwa bity na krawędź w optymalnej reprezentacji), a wykres jest gęsty. Jeśli entropia jest znacznie większa niż 2, a zwłaszcza jeśli jest zbliżona do wielkości wskaźnika, wykres jest rzadki. $p = \frac{E}{N^2}$ $- \log_2{p(1-p)}$ $p \approx \frac{1}{2}$

Pseudonim
źródło