Lista sąsiedztwa i macierzowa reprezentacja wykresu
Sara Chen
⚡ Inteligentne podsumowanie
Lista sąsiedztwa i macierzowa reprezentacja grafu przechowują wierzchołki i krawędzie w pamięci, umożliwiając algorytmom przechodzenie przez sieci. Lista sąsiedztwa wykorzystuje listy powiązane dla każdego wierzchołka, natomiast macierz sąsiedztwa wykorzystuje kwadratową, dwuwymiarową siatkę.
Mimo że wyglądają inaczej, wszyscy rodzaje wykresów można przedstawić w podobny sposób. Istnieją dwa rodzaje reprezentacji graficznej:
- Macierz sąsiedztwa
- Lista sąsiedztwa
Lista sąsiedztwa
Lista sąsiedztwa składa się z list powiązanych. Każdy wierzchołek jest traktowany jako indeks tablicy, a każdy element reprezentuje listę powiązaną. Te listy powiązane zawierają wierzchołki, które mają wspólną krawędź z wierzchołkiem indeksowanym.
Oto przykład listy sąsiedztwa:
Niech graf zawiera V wierzchołków i E krawędzi. Złożoność przestrzenna listy sąsiedztwa wynosi O(V + E), który skaluje się wraz z liczbą rzeczywistych krawędzi, a nie każdej możliwej pary wierzchołków.
W najgorszym przypadku złożoność przestrzeni staje się O(V²) jeśli dany graf jest grafem zupełnym, ponieważ każdy wierzchołek łączy się z każdym innym wierzchołkiem.
Macierz sąsiedztwa
Macierz sąsiedztwa składa się z tablicy 2D. W przypadku grafu z V wierzchołkami rozmiar macierzy będzie wynosił V × V.
Mówić matrix[i][j] = 5Oznacza to, że istnieje krawędź pomiędzy węzłem i i węzłem j, której waga wynosi 5.
Przyjrzyjmy się poniższemu grafowi i jego macierzy sąsiedztwa:
Zbudowaliśmy Tablica 2D korzystając z tych kroków:
Krok 1) Wierzchołek A ma bezpośrednią krawędź z wierzchołkiem B, a waga wynosi 5. Zatem komórka w wierszu A i kolumnie B zostanie wypełniona wartością 5. Pozostałe komórki w wierszu A zostaną wypełnione wartością zerową.
Krok 2) Wierzchołek B ma bezpośrednią krawędź z C, a waga wynosi 4. Zatem komórka w wierszu B i kolumnie C zostanie wypełniona wartością 4. Pozostałe komórki w wierszu B zostaną wypełnione wartością zerową, ponieważ B nie ma krawędzi wychodzącej do żadnego innego węzła.
Krok 3) Wierzchołek C nie ma krawędzi bezpośrednich z żadnym innym wierzchołkiem. Dlatego wiersz C zostanie wypełniony zerami.
Krok 4) Wierzchołek D ma skierowaną krawędź z A i C.
- Komórka w wierszu D i kolumnie A będzie miała wartość 7. Komórka w wierszu D i kolumnie C będzie miała wartość 2.
- Pozostałe komórki w wierszu D zostaną wypełnione zerami.
Krok 5) Wierzchołek E ma skierowaną krawędź z B i D. Komórka w wierszu E i kolumnie B będzie miała wartość 6. Komórka w wierszu E i kolumnie D będzie miała wartość 3. Pozostałe komórki w wierszu E będą wypełnione zerami.
Oto kilka punktów, na które warto zwrócić uwagę:
- Graf nie posiada pętli własnych, gdy przekątna główna macierzy sąsiedztwa jest równa 0.
- Graf jest grafem skierowanym, jeśli komórki w punktach (a, b) i (b, a) nie mają tej samej wartości. W przeciwnym razie graf jest nieskierowany.
- Wykres jest wykresem ważonym, jeżeli wartość dowolnej komórki jest większa od 1.
Głównym problemem macierzy sąsiedztwa jest to, że wymaga ona kwadratowej przestrzeni. Nawet nieistniejące krawędzie nadal przydzielają komórki w pamięci.
Na przykład, jeśli mamy graf z 100 węzłami, to do jego zapisania potrzeba 10 000 komórek. RAMPrzy mniejszej liczbie krawędzi w grafie przydzielanie tak dużej ilości pamięci może być marnotrawstwem. Zatem złożoność pamięci przy użyciu macierzy sąsiedztwa wynosi O(N²), gdzie N jest liczbą węzłów na grafie.
Lista sąsiedztwa kontra macierz sąsiedztwa
Przed wybraniem reprezentacji warto porównać oba modele obok siebie w odniesieniu do operacji dominujących w rzeczywistych obciążeniach grafów:
| Operacja | Macierz sąsiedztwa | Lista sąsiedztwa |
|---|---|---|
| Złożoność przestrzeni | O(V²) | O(V + E) |
| Dodaj wierzchołek | O(V²) | O (1) |
| Dodaj krawędź | O (1) | O (1) |
| Usuń krawędź | O (1) | O(E) |
| Sprawdź czy krawędź (i, j) istnieje | O (1) | O(stopień i) |
| Iteruj po sąsiadach i | O (V) | O(stopień i) |
| Najlepszy dla | Gęste grafy, częste zapytania krawędziowe | Rzadkie grafy, zadania wymagające intensywnego przechodzenia |
Krótko mówiąc, macierz sąsiedztwa wygrywa w przypadku wyszukiwań krawędzi w stałym czasie, natomiast lista sąsiedztwa wygrywa w przypadku iteracji pamięci i sąsiadów, dlatego algorytmy takie jak BFS, DFS i Dijkstra zwykle łączą się z listami sąsiedztwa.
Zalety i wady reprezentacji grafowej
Każda reprezentacja niesie ze sobą pewne kompromisy. Znajomość mocnych i słabych stron obu modeli pomoże Ci wybrać ten właściwy dla rozwiązywanego problemu.
Zalety macierzy sąsiedztwa:
- Zapytania o istnienie krawędzi w czasie stałym O(1) pomiędzy dowolną parą wierzchołków.
- Stałe indeksowanie ułatwia implementację algorytmów macierzowych, takich jak algorytm Floyda-Warshalla i domknięcie przechodnie.
- Obciążone krawędzie naturalnie pasują do pojedynczej komórki macierzy.
Wady macierzy sąsiedztwa:
- Marnuje O(V²) pamięci, gdy graf jest rzadki.
- Dodanie nowego wierzchołka wymaga zmiany rozmiaru całej macierzy.
- Iterowanie po sąsiadujących wierzchołkach zajmuje O(V) nawet wtedy, gdy wierzchołek ma tylko kilka krawędzi.
Zalety listy sąsiedztwa:
- Używa tylko pamięci O(V + E), co jest wartością zbliżoną do rzeczywistej liczby krawędzi w rzadkich grafach.
- Dodanie nowego wierzchołka lub krawędzi to O(1).
- Algorytmy przechodzenia, takie jak BFS i DFS, iterują po sąsiadach z dokładnością O(stopni), co daje łączny czas wykonania O(V + E).
Wady listy sąsiedztwa:
- Sprawdzenie, czy dana krawędź istnieje, zajmuje czas O(stopni) zamiast O(1).
- Lokalność pamięci podręcznej jest słabsza, ponieważ listy powiązane są rozproszone w pamięci.
- Krawędzie ważone wymagają pola towarzyszącego lub listy par, co nieco komplikuje strukturę danych.
Kiedy używać listy sąsiedztwa, a kiedy macierzy sąsiedztwa
Wybór reprezentacji zależy od gęstości grafu i najczęściej wykonywanych operacji. Skorzystaj z tego krótkiego przewodnika, aby wybrać odpowiednią strukturę:
- Preferuj macierz sąsiedztwa gdy graf jest gęsty (E jest bliskie V²), gdy krawędzie rzadko się zmieniają i gdy algorytm wielokrotnie pyta „czy istnieje krawędź między i i j?”.
- Preferuj listę sąsiedztwa gdy graf jest rzadki (E jest znacznie mniejsze niż V²), gdy zbiór wierzchołków lub krawędzi rośnie podczas wykonywania i gdy przemierzasz graf metodą BFS, DFS lub Algorytm najkrótszej ścieżki Dijkstry.
- Wolę model mieszany (lista sąsiedztwa plus zestaw skrótów krawędzi), gdy potrzebujesz zarówno szybkiej iteracji sąsiedztwa, jak i zapytań o krawędzie O(1), ale kosztem dodatkowej pamięci.
Nowoczesne biblioteki grafów, takie jak NetworkX i igraph, domyślnie korzystają z list sąsiedztwa, ponieważ większość rzeczywistych grafów — sieci społecznościowe, mapy drogowe, strony internetowe, zależności pakietów — jest rozproszona i wymaga intensywnego przeglądania.
