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|$vertical bar, v, vertical bar oznaczamy liczbami od 0 do $|V|-1$vertical bar, V, vertical bar, minus, 1. Poniżej pokazujemy przykład grafu sieci społecznej z 10 wierzchołkami oznaczanymi za pomocą liczb całkowitych zamiast nazw:

Jednym z najprostszych sposobów reprezentacji grafów jest lista lub tablica $|E|$vertical bar, E, vertical bar 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 $\Theta(E)$\Theta, left parenthesis, E, right parenthesis. Dla przykładu poniżej napisaliśmy jak należy zaprezentować listę krawędzi w języku JavaScript dla naszego grafu sieci społecznej:

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|$vertical bar, E, vertical bar krawędzi. Pozostaje pytanie... Jak zorganizować listę krawędzi by przeszukiwanie jej w celu znalezienia konkretnej krawędzi zajmowało czas $O(\lg E)$O, left parenthesis, \lg, E, right parenthesis? Odpowiedź nie jest taka oczywista.

Dla grafu z $|V|$vertical bar, V, vertical bar wierzchołkami macierzą sąsiedztwa (ang. adjacency matrix) nazywamy macierz o wymiarach $|V| \cdot |V|$vertical bar, V, vertical bar, dot, vertical bar, V, vertical bar 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)$left parenthesis, i, comma, j, right parenthesis 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:

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)$left parenthesis, i, comma, j, right parenthesis 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 $\Theta(V^2)$\Theta, left parenthesis, V, squared, right parenthesis 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|$vertical bar, V, vertical bar 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.

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|$vertical bar, V, vertical bar 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:

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)$left parenthesis, i, comma, j, right parenthesis 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 $\Theta(d)$\Theta, left parenthesis, d, right parenthesis, 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ż $|V|-1$vertical bar, V, vertical bar, minus, 1 (w przypadku gdy $i$i jest połączony krawędziami ze wszystkimi pozostałymi $|V|-1$vertical bar, V, vertical bar, minus, 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:

Jeśli zapis podwójnego indeksowania jest dla ciebie niezrozumiały, możesz pomyśleć o nim w inny sposób:

Ile pamięci zajmują listy sąsiedztwa? Mamy $|V|$vertical bar, V, vertical bar list i choć każda lista może liczyć do $|V|-1$vertical bar, V, vertical bar, minus, 1 wierzchołków, to w sumie listy sąsiedztwa dla grafu nieskierowanego zawierać będzie $2|E|$2, vertical bar, E, vertical bar elementów. Czemu $2|E|$2, vertical bar, E, vertical bar? Każda krawędź $(i,j)$left parenthesis, i, comma, j, right parenthesis 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|$vertical bar, E, vertical bar. Dla grafu skierowanego, listy sąsiedztwa zawierają łączną liczbę $|E|$vertical bar, E, vertical bar 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.