Trzy sposoby przechowywania wykresu w pamięci, zalety i wady

Istnieją trzy sposoby przechowywania wykresu w pamięci:

1. Węzły jako obiekty i krawędzie jako wskaźniki
2. Macierz zawierająca wszystkie wagi krawędzi między numerowanymi węzłami x i y
3. Lista krawędzi między numerowanymi węzłami

Wiem, jak napisać wszystkie trzy, ale nie jestem pewien, czy wymyśliłem wszystkie zalety i wady każdego z nich.

Jakie są zalety i wady każdego z tych sposobów przechowywania wykresu w pamięci?

Jednym ze sposobów ich analizy jest pamięć i złożoność czasowa (która zależy od tego, jak chcesz uzyskać dostęp do wykresu).

Przechowywanie węzłów jako obiektów ze wskaźnikami do siebie

• Złożoność pamięci dla tego podejścia wynosi O (n), ponieważ masz tyle obiektów, ile masz węzłów. Wymagana liczba wskaźników (do węzłów) wynosi maksymalnie O (n ^ 2), ponieważ każdy obiekt węzła może zawierać wskaźniki do maksymalnie n węzłów.
• Złożoność czasowa dla tej struktury danych wynosi O (n) dla dostępu do dowolnego danego węzła.

Przechowywanie macierzy wag krawędzi

• Byłaby to złożoność pamięci O (n ^ 2) dla macierzy.
• Zaletą tej struktury danych jest to, że złożoność czasowa dostępu do dowolnego danego węzła wynosi O (1).

W zależności od algorytmu uruchomionego na wykresie i liczby węzłów, będziesz musiał wybrać odpowiednią reprezentację.

Jeszcze kilka rzeczy do rozważenia:

1. Model macierzowy łatwiej nadaje się do tworzenia wykresów z ważonymi krawędziami, dzięki przechowywaniu wag w macierzy. Model obiektu / wskaźnika musiałby przechowywać wagi krawędzi w tablicy równoległej, co wymaga synchronizacji z tablicą wskaźników.

2. Model obiekt / wskaźnik działa lepiej z wykresami skierowanymi niż z wykresami nieukierunkowanymi, ponieważ wskaźniki musiałyby być utrzymywane w parach, które mogą stać się niezsynchronizowane.

Metoda obiektów i wskaźników ma trudności z wyszukiwaniem, jak niektórzy zauważyli, ale jest całkiem naturalna do robienia takich rzeczy, jak budowanie binarnych drzew wyszukiwania, gdzie jest dużo dodatkowej struktury.

Osobiście uwielbiam macierze sąsiedztwa, ponieważ znacznie ułatwiają wszelkiego rodzaju problemy, używając narzędzi z teorii grafów algebraicznych. (Na przykład k-ta potęga macierzy sąsiedztwa daje liczbę ścieżek o długości k od wierzchołka i do wierzchołka j. Dodaj macierz tożsamości przed pobraniem k-tej potęgi, aby uzyskać liczbę ścieżek o długości <= k. Weź rangę n-1 moll Laplacian, aby uzyskać liczbę rozpinanych drzew ... i tak dalej.)

Ale wszyscy mówią, że macierze sąsiedztwa są drogie w pamięci! Są tylko w połowie poprawne: możesz to obejść, używając rzadkich macierzy, gdy wykres ma kilka krawędzi. Rzadkie macierzowe struktury danych wykonują dokładnie pracę polegającą na utrzymywaniu listy przylegania, ale nadal mają pełną gamę dostępnych standardowych operacji macierzowych, zapewniając to, co najlepsze z obu światów.

Myślę, że twój pierwszy przykład jest trochę niejednoznaczny - węzły jako obiekty i krawędzie jako wskaźniki. Możesz je śledzić, przechowując tylko wskaźnik do jakiegoś węzła głównego, w którym to przypadku dostęp do danego węzła może być nieefektywny (powiedzmy, że chcesz węzła 4 - jeśli obiekt węzła nie jest dostarczony, może być konieczne wyszukanie go) . W takim przypadku stracisz również części wykresu, do których nie można dotrzeć z węzła głównego. Myślę, że tak właśnie jest w przypadku f64 rainbow, który przyjmuje, gdy mówi, że złożoność czasowa dostępu do danego węzła wynosi O (n).

W przeciwnym razie możesz również zachować tablicę (lub tablicę mieszającą) pełną wskaźników do każdego węzła. Umożliwia to O (1) dostęp do danego węzła, ale nieco zwiększa zużycie pamięci. Jeśli n jest liczbą węzłów, a e jest liczbą krawędzi, złożoność przestrzenna tego podejścia wyniosłaby O (n + e).

Złożoność przestrzeni dla podejścia macierzowego byłaby wzdłuż linii O (n ^ 2) (zakładając, że krawędzie są jednokierunkowe). Jeśli wykres jest rzadki, w macierzy będzie dużo pustych komórek. Ale jeśli twój wykres jest w pełni połączony (e = n ^ 2), wypada to korzystnie w porównaniu z pierwszym podejściem. Jak mówi RG, przy takim podejściu możesz mieć mniej błędów pamięci podręcznej, jeśli alokujesz macierz jako jeden fragment pamięci, co może przyspieszyć śledzenie wielu krawędzi wokół wykresu.

Trzecie podejście jest prawdopodobnie najbardziej efektywne pod względem miejsca w większości przypadków - O (e) - ale oznaczałoby, że znalezienie wszystkich krawędzi danego węzła byłoby zadaniem O (e). Nie przychodzi mi do głowy przypadek, w którym byłoby to bardzo przydatne.

Spójrz na tabelę porównawczą na Wikipedii. Daje całkiem dobre zrozumienie, kiedy należy używać każdej reprezentacji wykresów.

Jest jeszcze jedna opcja: węzły jako obiekty, krawędzie też jako obiekty, każda krawędź jest jednocześnie na dwóch podwójnie połączonych listach: lista wszystkich krawędzi wychodzących z tego samego węzła i lista wszystkich krawędzi wchodzących do tego samego węzła .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

Narzut pamięci jest duży (2 wskaźniki na węzeł i 6 wskaźników na krawędź), ale otrzymujesz

• Wstawienie węzła O (1)
• O (1) wstawienie krawędzi (podane wskaźniki do węzłów „od” i „do”)
• O (1) usunięcie krawędzi (biorąc pod uwagę wskaźnik)
• Usunięcie węzła O (deg (n)) (biorąc pod uwagę wskaźnik)
• O (deg (n)) znajdowanie sąsiadów węzła

Struktura może również przedstawiać raczej ogólny wykres: zorientowany multigraf z pętlami (tj. Możesz mieć wiele różnych krawędzi między tymi samymi dwoma węzłami, w tym wiele różnych pętli - krawędzie przechodzące od x do x).

Bardziej szczegółowe wyjaśnienie tego podejścia jest dostępne tutaj .

Okay, więc jeśli krawędzie nie mają wag, macierz może być tablicą binarną, a użycie operatorów binarnych może w tym przypadku sprawić, że wszystko pójdzie naprawdę, bardzo szybko.

Jeśli wykres jest rzadki, metoda obiektu / wskaźnika wydaje się znacznie wydajniejsza. Trzymanie obiektu / wskaźników w strukturze danych specjalnie w celu nakłonienia ich do jednego kawałka pamięci może być również dobrym planem lub inną metodą połączenia ich.

Lista sąsiedztwa - po prostu lista połączonych węzłów - wydaje się zdecydowanie najbardziej wydajna pod względem pamięci, ale prawdopodobnie również najwolniejsza.

Odwrócenie skierowanego wykresu jest łatwe w przypadku reprezentacji macierzowej i łatwe w przypadku listy sąsiedztwa, ale nie jest tak dobre w przypadku reprezentacji obiektu / wskaźnika.