Dla grafów można zdefiniować podstawowe interfejsy ADT,
czyli abstrakcyjnych typów danych, które będą używane przy
analizowaniu algorytmów grafowych.
Z drugiej strony, do reprezentacji grafu można wykorzystać
różne struktury danych, takie jak macierz sąsiedztwa,
lista sąsiedztwa, lista krawędzi.
Pewne rodziny grafów mają inne wydajne reprezentacje
(grafy przedziałowe, grafy permutacji).
Jeżeli graf prosty nieskierowany ma n wierzchołków, to liczba możliwych
zbiorów krawędzi wynosi 2^{n(n-1)/2}. Stąd każda reprezentacja grafu musi
używać co najmniej n(n-1)/2 bitów w najgorszym i średnim przypadku,
O(n^2) bitów.
- Macierz sąsiedztwa (adjacency-matrix).
Graf przedstawiamy jako tablicę kwadratową A,
gdzie wiersze i kolumny są numerowane wierzchołkami.
Jeżeli istnieje krawędź (u,v), to A[u,v] wynosi 1 (True).
W przeciwnym wypadku A[u,v] wynosi 0 (False).
Reprezentacja ta jest wydajna dla grafów gęstych z dużą liczbą krawędzi.
Wykorzystanie pamięci jest rzędu O(n^2) [liczba bitów dla grafu bez wag].
Do takiej tablicy łatwo można wpisywać wagi dla każdej krawędzi.
Reprezentacja jest też przydatna w sytuacji, gdy chcemy szybko
sprawdzić istnienie krawędzi między dwoma wierzchołkami [Cormen].
graph = [
[0, 1, 0, 0],
[0, 0, 1, 0],
[1, 0, 0, 1],
[0, 1, 0, 0]] # wagi (lub bity 0/1)
- Listy sąsiedztwa (adjacency-list).
Każdemu wierzchołkowi v przyporządkowujemy
listę wierzchołków, do których można dojść z wierzchołka v.
Reprezentacja ta jest wydajna dla rzadkich grafów z małą liczbą krawędzi.
Wierzchołki zwykle oznaczami liczbami, a liczba bitów potrzebna do zapisania
liczby n to O(log n).
Dla grafu skierowanego mamy m elementów na listach sąsiedztwa,
a dla grafu nieskierowanego 2m elementów.
Wykorzystanie pamięci jest rzędu O(m log n) bitów.
Dla rzadkich grafów dostajemy O(n log n) bitów,
ale dla gęstych O(n^2 log n) bitów pamięci.
W przypadku grafów z wagami, na liście sąsiedztwa można przechowywać
wierzchołek końcowy łącznie z wagą krawędzi, która do niego prowadzi.
graph = [[1], [2], [0, 3], [1]] # bez wag (styl C++)
graph = {0: [1], 1: [2], 2: [0, 3], 3: [1]} # bez wag (styl GvR)
graph = {0: set([1]), 1: set([2]), 2: set([0, 3]), 3: set([1])} # bez wag (zbiory)
graph = {0: [(1,1)], 1: [(2,1)], 2: [(0,1), (3,1)], 3: [(1,1)]} # wagi (dict+list)
graph = {0: {1: 1}, 1: {2: 1}, 2: {0: 1, 3: 1}, 3: {1: 1}} # wagi (dict+dict)
graph = {0: {1: Edge(0, 1, 1)},
1: {2: Edge(1, 2, 1)},
2: {0: Edge(2, 0, 1), 3: Edge(2, 3, 1)},
3: {1: Edge(3, 1, 1)}} # wagi w pakiecie 'graphtheory'
graph = {0: {1: {'weight': 1}},
1: {2: {'weight': 1}},
2: {0: {'weight': 1}, 3: {'weight': 1}},
3: {1: {'weight': 1}}} # wagi w NetworkX
- Lista krawędzi.
Zapamiętujemy listę krawędzi grafu.
Wykorzystanie pamięci jest rzędu O(m log n) bitów, bo mamy m par liczb
dla grafu bez wag.
W tym podejściu nie zapiszemy pustych wierzchołków.
graph = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 1)] # bez wag
graph = [(0, 1, 1), (1, 2, 1), (2, 0, 1), (2, 3, 1), (3, 1, 1)] # wagi
graph = [Edge(0, 1, 1), Edge(1, 2, 1), Edge(2, 0, 1), Edge(2, 3, 1), Edge(3, 1, 1)] # wagi
- Macierz incydencji.
Graf przedstawiamy jako tablicę prostokątną M,
gdzie wiersze są numerowane wierzchołkami,
a kolumny krawędziami.
W kolumnie odpowiadającej danej krawędzi -1 oznacza
wierzchołek początkowy, a +1 wierzchołek końcowy.
Dla grafu nieskierowanego oba końce krawędzi oznacza się przez 1.
Pętlę można zaznaczyć przez 2 w danym wierzchołku.
Wykorzystanie pamięci jest rzędu O(n m) bitów.
graph = [
[-1, 0, 1, 0, 0],
[ 1,-1, 0, 0, 1],
[ 0, 1,-1,-1, 0],
[ 0, 0, 0, 1,-1]] # bez wag
# Chyba wygodniej byłoby mieć macierz transponowaną.