Reprezentacje grafów - macierz sąsiedztwa i lista

Wprowadzenie

Aby efektywnie pracować z grafami w programowaniu, musimy wybrać odpowiednią strukturę danych do ich reprezentacji. Wybór reprezentacji wpływa na: - Wydajność operacji (dodawanie, usuwanie, wyszukiwanie) - Zużycie pamięci - Prostotę implementacji algorytmów

W tej lekcji poznamy trzy główne reprezentacje grafów: 1. Macierz sąsiedztwa (Adjacency Matrix) 2. Lista sąsiedztwa (Adjacency List) 3. Lista krawędzi (Edge List)

1. Macierz sąsiedztwa (Adjacency Matrix)

Definicja

Macierz sąsiedztwa to dwuwymiarowa tablica A[n][n], gdzie n = liczba wierzchołków.

Dla grafu nieskierowanego:

A[i][j] = 1   jeśli istnieje krawędź między wierzchołkiem i a j
A[i][j] = 0   w przeciwnym razie

Dla grafu ważonego:

A[i][j] = waga   jeśli istnieje krawędź
A[i][j] = ∞      jeśli nie ma krawędzi (lub 0, w zależności od konwencji)

Przykład - graf nieskierowany

Graf:
    0 --- 1
    |     |
    3 --- 2

Krawędzie: {0,1}, {0,3}, {1,2}, {2,3}

Macierz sąsiedztwa:
     0  1  2  3
  0 [0  1  0  1]
  1 [1  0  1  0]
  2 [0  1  0  1]
  3 [1  0  1  0]

Uwaga: Macierz jest SYMETRYCZNA (A[i][j] = A[j][i])

Przykład - graf skierowany

Graf:
    0 → 1
    ↓   ↓
    3 ← 2

Krawędzie: (0,1), (0,3), (1,2), (2,3)

Macierz sąsiedztwa:
     0  1  2  3
  0 [0  1  0  1]
  1 [0  0  1  0]
  2 [0  0  0  1]
  3 [0  0  0  0]

Uwaga: Macierz NIE jest symetryczna
A[i][j] = 1 oznacza krawędź i → j

Implementacja w Pythonie

Wyjście:

Graf nieskierowany:
      0  1  2  3
 0    0  1  0  1
 1    1  0  1  0
 2    0  1  0  1
 3    1  0  1  0

Sąsiedzi wierzchołka 0: [(1, 1), (3, 1)]
Stopień wierzchołka 1: 2
Czy istnieje krawędź 0-2? False


Graf skierowany:
      0  1  2  3
 0    0  1  0  1
 1    0  0  1  0
 2    0  0  0  1
 3    0  0  0  0

Następniki wierzchołka 0: [(1, 1), (3, 1)]

Zalety macierzy sąsiedztwa

✅ Szybkie sprawdzanie krawędzi: O(1) ✅ Prosta implementacja ✅ Łatwe dodawanie/usuwanie krawędzi: O(1) ✅ Dobre dla algorytmów wymagających szybkiego sprawdzania sąsiedztwa

Wady macierzy sąsiedztwa

❌ Duże zużycie pamięci: O(V²) nawet dla rzadkich grafów ❌ Wolne iterowanie po sąsiadach: O(V) zamiast O(deg(v)) ❌ Trudność z dynamicznym dodawaniem wierzchołków (trzeba realokować całą macierz)

2. Lista sąsiedztwa (Adjacency List)

Definicja

Lista sąsiedztwa to tablica list, gdzie dla każdego wierzchołka v przechowujemy listę jego sąsiadów.

Dla każdego wierzchołka v:
  adj[v] = lista wierzchołków sąsiadujących z v

Dla grafu ważonego:

adj[v] = lista tupli (sąsiad, waga)

Przykład - graf nieskierowany

Graf:
    0 --- 1
    |     |
    3 --- 2

Lista sąsiedztwa:
0 → [1, 3]
1 → [0, 2]
2 → [1, 3]
3 → [0, 2]

Przykład - graf skierowany

Graf:
    0 → 1
    ↓   ↓
    3 ← 2

Lista sąsiedztwa:
0 → [1, 3]
1 → [2]
2 → [3]
3 → []

Implementacja w Pythonie

Wyjście:

Graf nieskierowany:
0 → ['1(w=5)', '3(w=3)']
1 → ['0(w=5)', '2(w=2)']
2 → ['1(w=2)', '3(w=4)']
3 → ['0(w=3)', '2(w=4)']

Sąsiedzi wierzchołka 0: [(1, 5), (3, 3)]
Stopień wierzchołka 1: 2
Czy istnieje krawędź 0-2? False


Graf skierowany:
A → ['B(w=1)', 'C(w=1)']
B → ['C(w=1)']
C → ['D(w=1)']
D → []

Zalety listy sąsiedztwa

✅ Oszczędność pamięci: O(V + E) zamiast O(V²) ✅ Szybkie iterowanie po sąsiadach: O(deg(v)) ✅ Łatwe dodawanie wierzchołków: O(1) ✅ Dobre dla rzadkich grafów (sparse graphs)

Wady listy sąsiedztwa

❌ Wolniejsze sprawdzanie krawędzi: O(deg(v)) zamiast O(1) ❌ Usuwanie krawędzi wymaga przeszukania listy: O(deg(v))

3. Lista krawędzi (Edge List)

Definicja

Lista krawędzi to prosta lista wszystkich krawędzi w grafie.

Dla grafu nieskierowanego: [(u, v), ...]
Dla grafu ważonego: [(u, v, waga), ...]

Implementacja w Pythonie

Wyjście:

Graf jako lista krawędzi:
0 --- 1 (waga: 5)
0 --- 3 (waga: 3)
1 --- 2 (waga: 2)
2 --- 3 (waga: 4)

Wierzchołki: {0, 1, 2, 3}
Liczba krawędzi: 4

Zalety listy krawędzi

✅ Bardzo prosta implementacja ✅ Minimalne zużycie pamięci: O(E) ✅ Dobre dla algorytmów przetwarzających wszystkie krawędzie (np. Kruskal)

Wady listy krawędzi

❌ Bardzo wolne znajdowanie sąsiadów: O(E) ❌ Wolne sprawdzanie krawędzi: O(E) ❌ Nieefektywne dla większości algorytmów grafowych

Porównanie reprezentacji

Tabela złożoności

Operacja	Macierz sąsiedztwa	Lista sąsiedztwa	Lista krawędzi
Pamięć	O(V²)	O(V + E)	O(E)
Dodaj wierzchołek	O(V²)	O(1)	O(1)
Dodaj krawędź	O(1)	O(1)	O(1)
Usuń krawędź	O(1)	O(V)	O(E)
Sprawdź krawędź	O(1)	O(V)	O(E)
Znajdź sąsiadów	O(V)	O(deg(v))	O(E)
Iteruj po krawędziach	O(V²)	O(V + E)	O(E)

Kiedy używać której reprezentacji?

Macierz sąsiedztwa

Użyj gdy: - Graf jest gęsty (duża liczba krawędzi, E ≈ V²) - Często sprawdzasz czy istnieje krawędź między dwoma wierzchołkami - Implementujesz algorytmy wymagające szybkiego dostępu do wag krawędzi (np. Floyd-Warshall)

Przykłady zastosowań: - Graf pełny lub prawie pełny - Algorytmy najkrótszej ścieżki dla wszystkich par (Floyd-Warshall) - Problemy dopasowania w grafach dwudzielnych

Lista sąsiedztwa

Użyj gdy: - Graf jest rzadki (mała liczba krawędzi, E << V²) - Często iterujesz po sąsiadach wierzchołka - Dynamicznie dodajesz/usuwasz wierzchołki

Przykłady zastosowań: - BFS, DFS (przeszukiwanie grafów) - Algorytm Dijkstry - Większość rzeczywistych grafów (sieci społecznościowe, internet, mapy)

Lista krawędzi

Użyj gdy: - Przetwarzasz wszystkie krawędzie naraz - Sortujesz krawędzie według wagi - Graf jest bardzo prosty

Przykłady zastosowań: - Algorytm Kruskala (MST) - Algorytmy sortujące krawędzie - Proste analizy grafów

Przykład praktyczny: Porównanie wydajności

Przykładowe wyniki:

=== Graf RZADKI ===
Graf: V=100, E=200
Gęstość: 4.04%

Reprezentacja        Budowa (s)      1000 sprawdzeń (s)
-------------------------------------------------------
Macierz sąsiedztwa   0.000234        0.000012
Lista sąsiedztwa     0.000089        0.001234
Lista krawędzi       0.000045        0.023456

Wnioski: Lista sąsiedztwa najszybsza do budowy, macierz najszybsza do sprawdzania


=== Graf GĘSTY ===
Graf: V=100, E=3000
Gęstość: 60.61%

Reprezentacja        Budowa (s)      1000 sprawdzeń (s)
-------------------------------------------------------
Macierz sąsiedztwa   0.002345        0.000012
Lista sąsiedztwa     0.001234        0.003456
Lista krawędzi       0.000678        0.145678

Wnioski: Dla gęstego grafu, macierz jest konkurencyjna

Konwersje między reprezentacjami

Macierz → Lista sąsiedztwa

Lista sąsiedztwa → Macierz

Podsumowanie

Wybór reprezentacji - szybki przewodnik

Co dalej?

Po zrozumieniu reprezentacji grafów, następne kroki to:

Lekcja 56: Przeszukiwanie wszerz (BFS)
Algorytm BFS
Najkrótsza ścieżka w grafie nieważonym
Poziomy grafu
Lekcja 57: Przeszukiwanie w głąb (DFS)
Algorytm DFS
Wykrywanie cykli
Sortowanie topologiczne
Lekcja 58: Algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym
Implementacja z kolejką priorytetową

Zadania praktyczne

Zadanie 1: Transpozycja grafu

Dla grafu skierowanego, zaimplementuj funkcję zwracającą graf transponowany (wszystkie krawędzie odwrócone).

Zadanie 2: Gęstość grafu

Napisz funkcję obliczającą gęstość grafu i klasyfikującą go jako "rzadki", "średni" lub "gęsty".

Zadanie 3: Komplementarny graf

Zaimplementuj funkcję zwracającą graf komplementarny (krawędzie istnieją tam, gdzie ich nie było, i na odwrót).

Zadanie 4: Benchmark własny

Stwórz własny benchmark porównujący reprezentacje dla konkretnego przypadku użycia (np. sieć społecznościowa, mapa drogowa).

Następna lekcja: Przeszukiwanie wszerz (BFS) - pierwszy algorytm przeszukiwania grafów