Reprezentacja grafów

6.1 Macierz sąsiedztwa: zasada działania, zalety i wady.

Macierz sąsiedztwa to sposób reprezentacji grafu w postaci kwadratowej macierzy o rozmiarze n x n, gdzie n to liczba wierzchołków w grafie. Elementy macierzy wskazują na obecność lub brak krawędzi między wierzchołkami:

• Jeżeli istnieje krawędź między wierzchołkami i i j, to element A[i][j] = 1 (lub waga krawędzi, jeśli graf jest ważony).
• Jeśli krawędzi nie ma, to A[i][j] = 0.

Przykład:

Dla grafu z wierzchołkami A, B, C i krawędziami (A, B), (B, C) i (C, A) macierz sąsiedztwa będzie wyglądała tak:

Gdyby wszystkie wierzchołki były połączone ze sobą, to macierz sąsiedztwa wyglądałaby tak:

Zalety:

• Prostota: łatwa do zrozumienia i wdrożenia.
• Szybki dostęp: sprawdzenie istnienia krawędzi między dwoma wierzchołkami zajmuje O(1).
• Odpowiednia dla gęstych grafów: efektywna dla grafów z dużą liczbą krawędzi.

Wady:

• Wysokie zużycie pamięci: wymaga O(n^2) pamięci, nawet jeśli graf zawiera mało krawędzi (graf rzadki).
• Nieefektywność dla rzadkich grafów: przy dużej liczbie wierzchołków i małej liczbie krawędzi większość elementów macierzy będzie zerami, co prowadzi do nieefektywnego wykorzystania pamięci.

6.2 Listy sąsiedztwa: zasada działania, zalety i wady.

Listy sąsiedztwa to sposób reprezentacji grafu w formie tablicy list. Każdy element tablicy odpowiada wierzchołkowi grafu i zawiera listę wszystkich sąsiednich wierzchołków.

Przykład:

Dla grafu z wierzchołkami A, B, C i krawędziami (A, B), (B, C) i (C, A) listy sąsiedztwa będą wyglądały następująco:

Gdyby wszystkie wierzchołki były połączone ze sobą, listy sąsiedztwa wyglądałyby następująco:

Zalety:

• Efektywne wykorzystanie pamięci: wymaga O(V + E) pamięci, gdzie V to liczba wierzchołków, a E to liczba krawędzi, co czyni go bardziej odpowiednim dla rzadkich grafów.
• Łatwość przeglądania: dogodny do wykonywania operacji przeglądania grafu (na przykład, przeszukiwanie wszerz lub w głąb).

Wady:

• Bardziej złożony dostęp: sprawdzenie istnienia krawędzi między dwoma wierzchołkami wymaga O(k) czasu, gdzie k to liczba sąsiadów wierzchołka.
• Mniej oczywista struktura: bardziej złożona w implementacji i zrozumieniu w porównaniu z macierzą sąsiedztwa.

6.3 Porównanie różnych metod reprezentacji grafów.

Sporównajmy różne metody reprezentacji grafów.

1. Macierz sąsiedztwa:

• Prostota: łatwa do zrozumienia i wdrożenia.
• Pamięć: wymaga O(n^2) pamięci, co może być nieefektywne dla rzadkich grafów.
• Szybkość dostępu: sprawdzenie istnienia krawędzi wykonuje się w czasie O(1).
• Odpowiednia: dla gęstych grafów z dużą liczbą krawędzi.

2. Listy sąsiedztwa:

• Prostota: mniej oczywiste niż macierz sąsiedztwa, ale także zrozumiałe.
• Pamięć: wymagają O(V + E) pamięci, co jest bardziej efektywne dla rzadkich grafów.
• Szybkość dostępu: sprawdzenie istnienia krawędzi wykonuje się w czasie O(k), gdzie k to liczba sąsiadów wierzchołka.
• Odpowiednie: dla rzadkich grafów z małą liczba krawędzi.

Porównanie:

Macierz sąsiedztwa jest lepsza dla gęstych grafów, gdzie większość wierzchołków jest połączona krawędziami, ponieważ zapewnia szybki dostęp do informacji o krawędziach i jest prosta w realizacji.

Listy sąsiedztwa są bardziej odpowiednie dla rzadkich grafów, gdzie liczba krawędzi jest znacznie mniejsza, niż liczba możliwych par wierzchołków. Zapewniają efektywne wykorzystanie pamięci i są dogodnie używane przy wykonywaniu operacji przeglądania grafu.