ALG - Reprezentacje grafów

by NOWIESZ

Wprowadzonko:

Graf to po prostu zbiór wierzchołków połączonych ze sobą na różne sposoby krawędziami. Skupię się tutaj na grafach skierowanych (rozróżnia się początkowy i końcowy wierzchólek krawędzi). Nie będę rozważać multigrafów (czyli między parą wierzchołków mogą wystąpić co najwyżej dwie krawędzie o przeciwnym kierunku).
Liczbę wierzchołków będę oznaczać przez V (i numerować 1..V), a liczbę krawędzi przez E. Oczywiście V2>=E. Grafy, w których E=V2 nazywamy pełnymi, E jest trochę mniejsze od V2 - gęstymi, a dużo mniejsze - rzadkimi.
Problem jest taki, że należy te grafy jakoś zapisać w pamięci. Można go rozwiązać na kilka sposobów. Każdy ma swoje wady i zalety w zależności od gęstości grafu i operacji na nim wykonywanych.


Lista krawędzi:

Chyba najprostszą reprezentacją, a zpewnością wymagającą najmniej wyobraźni, jest lista krawędzi. To po prostu wrzucone na liste pary wierzchołków (początki i końce krawędzi) bez żadnej specjalnej kolejności.

Ta metoda jest mało efektywna ze względu na to, że wykonanie dowolnej z powyższych operacji zmusza nas do przeszukania całej listy.


Macierz incydencji:

Macierz incydencji składa się z V wierszy (odpowiadającym wierzchołkom) i E kolumn (odpowiadającym krawędziom). Na "skrzyżowaniu" wierzchołka z krawędzią jest -1 gdy krawędź wychodzi z wierzchołka, +1 - krawędź wchodzi, 2 - pętla, 0 - brak incydencji.

Szczerze mówiąc jest to najgorsza z możliwych reprezentacji i nawet najgorszemu wrogowi nie życzyłbym wymyślenia takiej. Choć możliwe, że o czymś nie wiem, co uczyniłoby tą metodę choć trochę użyteczną.


Listy sąsiedztwa:

Reprezentacja grafów przez listy sąsiedztwa, jak sama nazwa wskazuje, polega na trzymaniu dla każdego wierzchołka listy jego wszystkich sąsiadów (następników albo poprzedników).

Jest to moim zdaniem najlepsza reprezentacja: minimalna możliwa złożoność pamięciowa, szybkie przeszukiwanie krawędzi wychodzących z danego wierzchołka, stosunkowo łatwa implementacja.
Wadą jest jedynie długi czas sprawdzenia istnienia pojedyńczej krawędzi. Można go poprawić do O(log V) wprowadzając drzewa BST (albo nawet drzewa zrównoważone) zamiast list, ale to skomplikuje implementację. Jednak raczej nie jest to potrzebne, bo wszystkie znane mi algorytmy nie korzystają z tej operacji - opierają się jedynie na przejrzeniu listy następników wierzchołka.


Macierz sąsiedztwa:

Macierz sąsiedztwa ma wymiary VxV. Idea jest prosta: jeżeli na "skrzyżowaniu" i-tego wiersza i j-tej kolumny znajduje się 1 to znaczy, że istnieje krawędź (i,j) (wychodząca z i-tego wierzchołka i wchodząca do j-tego); jeśli 0 to znaczy, że tej krawędzi nie ma.

Wadą tej reprezentacji jest duża złożoność pamięciowa i czasy przejrzenia większej liczby krawędzi. Dla grafów gęstych jest to niezauważalne, ale dla grafów rzadkich zdecydowanie polecam poprzednią metodę.
Zaletą jest możliwość szybkiego sprawdzenia czy dana krawędź istnieje (ale jak już wcześniej mówiłem, raczej to nie jest potrzebne). Ale niepodwarzalną zaletą jest duża prostota implementacji - łatwo, szybko i bezboleśnie.


Macierz grafu:

Najbardziej skomplikowaną z powyższych reprezentacji jest macierz grafu, wymyślona przez drużynę samego pdhiJB. Ma ona wymiary VxV, ale w odróżnieniu od macierzy sąsiedztwa nie zawiera jedynie zer i jedynek, a liczby z trzech możliwych przedziałów: (1) 1..V, (2) V+1..2*V, (3) -V..-1. Gdy liczba w i-tym wierszu i j-tej kolumnie jest z przedziału (1) to istnieje krawędź (i,j); gdy z przedziału (2) - istnieje krawędź (j,i); z przedziału (3) - nie istnieje krawędź między i-tym i j-tym wierzchołkiem.
Cały jednak sekret polega na tym, że w tej liczbie zakodowany jest nie tylko typ incydencji wierzchołków i-tego i j-tego, ale także "wskaźnik" na kolejny wierzchołek będący z i-tym w takiej samej incydencji jak j-ty. Tak na chłopski rozum to oto chodzi, że w i-tym wierszu macierzy są schowane trzy listy: lista następników i-tego wierzchołka, lista jego poprzedników, lista wierzchołków nieincydentnych z i-tym.
Mamy do czynienia z listami, więc trzeba zaznaczyć ich początki i końce. Koniec można łatwo zaznaczyć w taki sposób, że ostatni element wskazuje na samego siebie. Potrzebna nam jest dodatkowa struktura na zaznaczenie początków wszystkich list (można użyć do tego osobnych tablic, albo dopisać je na skrajach macierzy). Gdy jakaś lista jest pusta to można jako jej początek wpisać 0.

Wyjaśnienie jest nieco pokrętne, więc postanowiłem zaprezentować przykładowy graf wraz z jedną z możliwych macierzy dla niego. Zaznaczyłem też strzałeczkami, dla lepszego zrozumienia, kilka list (nie wszystkie, żeby nie zaciemniać rysunku), zaszytych w wierszach macierzy. W trzech tablicach na lewo od macierzy są zapisane początki odpowiednio list: następników, poprzedników, braku incydencji.

Ta metoda jest ulepszeniem metody listowej o szybki czas sprawdzenia istnienia krawędzi, kosztem zwiększenia złożoności pamięciowej (która przy grafach gęstych wcale się nie pogarsza).