Reprezentowanie grafów

Istnieje kilka sposobów reprezentowania grafów. Każde z nich ma swoje zalety i wady. Niektóre sytuacje czy algorytmy grafowe wymagają by na wejściu podać specyficzną reprezentację. W tym artykule przedstawimy trzy sposoby reprezentowania grafów.
Każdą z tych metod opiszemy za pomocą trzech kryteriów. Pierwsze kryterium to ile pamięci potrzebujemy użyć dla danej reprezentacji. Użyjemy do tego notacji asymptotycznej. Tak! Możemy użyć notacji asymptotycznej do innych celów niż tylko wyrażanie czasu wykonania algorytmu! Tak naprawdę notacja asymptotyczna służy do charakteryzowania funkcji, a funkcje mogą opisywać czas wykonania programu, ilość wymaganej przestrzeni jak również dowolne inne zasoby. Pozostałe dwa kryteria odnoszą się do czasu. Drugie kryterium to ile czasu zajmuje określenie położenia wybranej krawędzi. Ostatnie to określenie ile czasu będzie trwało znalezienie sąsiadów danego wierzchołka.
Jest powszechne, by identyfikować wierzchołki nie za pomocą imion (takich jak "Audrey", "Boston" czy "sweter"), ale używając liczb. Oznacza to, że najczęściej wierzchołki v |v| oznaczamy liczbami od 0 do V1 |V|-1 . Poniżej pokazujemy przykład grafu sieci społecznej z 10 wierzchołkami oznaczanymi za pomocą liczb całkowitych zamiast nazw:

Listy krawędzi

Jednym z najprostszych sposobów reprezentacji grafów jest lista lub tablica E |E| krawędzi, którą nazywamy listą krawędzi. By przedstawić krawędź wystarczy użyć tablicy dwuelementowej, zawierającej dwie liczby oznaczające wierzchołki lub tablicy obiektów, zawierającą informację o tym, które z wierzchołków są incydentne z daną krawędzią. Jeśli krawędzie mają wagi to dodaj do tablicy dwuelementowej liczbę mówiącą o tej wadze albo dodaj więcej informacji do obiektu w tablicy. Tak więc dla obu przypadków dla każdej krawędzi potrzebujemy dwóch lub trzech liczb by ją zaprezentować. Zatem całkowita przestrzeń zajmowana przez listę krawędzi to Θ(E) \Theta(E) . Dla przykładu poniżej napisaliśmy jak należy zaprezentować listę krawędzi w języku JavaScript dla naszego grafu sieci społecznej:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
Reprezentacja za pomocą list krawędzi jest prosta. Jednak gdy chcemy dowiedzieć się czy graf posiada daną krawędź musimy przeszukać całą listę. Jeśli krawędzie w liście nie są specjalnie uporządkowane, to mamy do czynienia z przeszukiwaniem liniowym przez wszystkie E |E| krawędzi. Pozostaje pytanie... Jak zorganizować listę krawędzi by przeszukiwanie jej w celu znalezienia konkretnej krawędzi zajmowało czas O(lgE) O(\lg E) ? Odpowiedź nie jest taka oczywista.

Macierz sąsiedztwa

Dla grafu z V |V| wierzchołkami macierzą sąsiedztwa (ang. adjacency matrix) nazywamy macierz o wymiarach VV |V| \cdot |V| złożoną z zer i jedynek, w której wartość w i i –tego wiersza i j j –tej kolumny jest równa 1 wtedy i tylko wtedy gdy krawędź (i,j) (i,j) występuje w grafie. Jeśli chcielibyśmy umieścić informacje o wagach krawędzi, wówczas zamiast 1 w i i –tym wierszu i j j –tej kolumnie powinniśmy umieścić wartość tej wagi. A w miejscach gdzie nie ma krawędzi (i wcześniej było 0) należy użyć specjalnej wartości (np. null). Poniżej przedstawiamy macierz adjacencji dla naszego przykładowego grafu sieci społecznej:
W JavaScript opisalibyśmy tę macierz tak:
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
Znalezienie czy dana krawędź występuje w grafie zajmuje teraz czas stały, gdyż wystarczy sprawdzić wartość elementu macierzy w odpowiednim miejscu. I tak na przykład jeśli macierz sąsiedztwa nazywa się graph, to możemy dowiedzieć się czy występuje w nim krawędź (i,j) (i,j) poprzez sprawdzenie wartości graph[i][j]. Jakie są więc wady macierzy sąsiedztwa? Właściwie są dwie. Pierwsza z nich to fakt, że zajmuje ona Θ(V2) \Theta(V^2) miejsca, nawet jeśli reprezentowany graf jest rzadki tzn. ma stosunkowo mało krawędzi. Innymi słowy, dla rzadkiego grafu macierz sąsiedztwa składa się głównie z zer. Używamy więc dużo miejsca by reprezentować niewiele krawędzi. Po drugie jeśli chcielibyśmy dowiedzieć się, które wierzchołki sąsiadują z danym wierzchołkiem i i , to musimy przejrzeć wszystkie V |V| wierzchołków w i i – tym wierszu, nawet jeśli niewielka liczba wierzchołków rzeczywiście z wierzchołkiem i i sąsiaduje.
Dla grafu nieskierowanego macierz sąsiedztwa jest symetryczna: wartość w i i –tym wierszu i j j –tej kolumnie wynosi 1 wtedy i tylko wtedy gdy wartość w j j –tym wierszu i i i –tej kolumnie również wynosi 1. W grafie skierowanym macierz sąsiedztwa nie musi być (i zazwyczaj nie jest) symetryczna.

Listy sąsiedztwa

Reprezentowanie grafu przy użyciu listy sąsiedztwa jest połączeniem macierzy sąsiedztwa i listy krawędzi. Dla każdego wierzchołka i i przechowywać będziemy tablicę wierzchołków sąsiadujących z nim. Zazwyczaj mamy tablicę V |V| list sąsiedztwa, jedną listę na każdy wierzchołek. I tutaj pokazujemy reprezentację za pomocą list sąsiedztwa dla naszego przykładu grafu sieci społecznej:
W języku JavaScript tak zaprezentowalibyśmy listy sąsiedztwa:
[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]
Numery wierzchołków w listach sąsiedztwa nie muszą występować w ustalonej kolejności. Jest jednak polecane, by listować je tak jak pokazano, w rosnącej kolejności.
Możemy teraz otrzymać listę sąsiedztwa dla danego wierzchołka w stałym czasie. Wystarczy wskazać na odpowiedni element w tablicy. Aby sprawdzić czy krawędź (i,j) (i,j) jest obecna w grafie, idziemy do listy sąsiedztwa dla wierzchołka i i w stałym czasie. Następnie w obrębie tej i i –tej listy szukamy czy występuje w niej element j j . Ile to potrwa w najgorszym wypadku? Odpowiedź to Θ(d) \Theta(d) , gdzie d d jest stopniem wierzchołka i i i jednocześnie długością listy sąsiedztwa i i –tego wierzchołka. Stopień wierzchołka i i może wynosić aż V1 |V|-1 (w przypadku gdy i i jest połączony krawędziami ze wszystkimi pozostałymi V1 |V|-1 wierzchołkami), ale może też równać się 0 (jeśli i i jest izolowany bez incydentnych krawędzi). W grafie nieskierowanym wierzchołek j j będzie na liście sąsiedztwa wierzchołka i i wtedy i tylko wtedy, gdy wierzchołek i i znajdzie się na liście sąsiedztwa wierzchołka j j . Jeśli graf jest ważony to wówczas elementami w listach sąsiedztwa są albo dwuelementowe tablice albo obiekty z informacją o numerze wierzchołka i wadze krawędzi.
Możesz użyć pętli for do iteracji przez wierzchołki w liście sąsiedztwa. Na przykład, załóżmy, że masz reprezentację grafu za pomocą list sąsiedztwa zapisaną w zmiennej graph tak, że graph[i] to tablica zawierająca sąsiadów i i –tego wierzchołka. Wtedy, aby wywołać jakąś funkcję doStuff na wszystkich wierzchołkach sąsiadujących z wierzchołkiem i i , użyjemy następującego kodu w JavaScripcie:
for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}
Jeśli zapis podwójnego indeksowania jest dla ciebie niezrozumiały, możesz pomyśleć o nim w inny sposób:
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}
Ile pamięci zajmują listy sąsiedztwa? Mamy V |V| list i choć każda lista może liczyć do V1 |V|-1 wierzchołków, to w sumie listy sąsiedztwa dla grafu nieskierowanego zawierać będzie 2E 2|E| elementów. Czemu 2E 2|E| ? Każda krawędź (i,j) (i,j) występuje dokładnie dwa razy w listach sąsiedztwa. Raz w liście i i , a drugi raz w liście j j . A krawędzi w grafie jest E |E| . Dla grafu skierowanego, listy sąsiedztwa zawierają łączną liczbę E |E| elementów. Jeden element odpowiadający każdej krawędzi.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Ładowanie