Poprzednia Następna

Każdy graf może być jednoznacznie reprezentowany na wiele sposobów. Dla człowieka w przypadku grafów o "rozsądnej" liczbie wierzchołków i krawędzi najwygodniejszy jest rysunek grafu. Pozostałe sposoby reprezentacji wykorzystywane są w komputerach. Każda z tych reprezentacji ma swoje wady i zalety, generalnie ograniczające są dwa warunki – ilość pamięci przeznaczonej na reprezentację i jej możliwości szybkiego odpowiadania na pytania typu czy między wierzchołkami v i u jest krawędź?. W przypadku grafów rzadkich listy sąsiedztwa okazują się wystarczająco szybkie by zrezygnować z pamięciożernych tablic. Najwygodniejszy dla człowieka jest rysunek grafu, reprezentujący wierzchołki i łączące je krawędzie. Wierzchołki oznaczane są zazwyczaj kropkami lub kołami, niekiedy zawierającymi indeksy bądź inne dodatkowe informacje. Krawędzie reprezentowane są krzywymi bądź prostymi, w przypadku krawędzi ważonych, waga umieszczona jest bezpośrednio nad krawędzią. Innymi najczęściej stosowanymi metodami reprezentacji grafów są macierze sąsiedztwa, listy sąsiedztwa i macierze incydencji. W przypadku implementacji algorytmów grafowych wybiera się tę metodę, za pomocą której dla danego problemu uzyska się program działający z mniejszą złożonością obliczeniową.

• Macierz sąsiedztwa
Najprostszą ze struktur danych umożliwiających przedstawienie skomplikowanego grafu lub jego przechowywanie w pamięci komputera jest macierz sąsiedztwa, zawierająca dane na temat połączeń między wierzchołkami. Macierz jest rozmiaru na , wyraz leżący z i-tego wiersza i j-tej kolumny zawiera wartość będącą liczbą krawędzi łączących i-ty i j-ty wierzchołek. Sposób ten pozwala na reprezentację zarówno grafów prostych, jak i grafów zawierających krawędzie wielokrotne oraz pętle własne. W przypadku grafów prostych wyrazami w macierzy będą wartości boole'owskie – jest krawędź, bądź nie ma krawędzi). Macierz sąsiedztwa wraz z grafem nieskierowanym odpowiadającym tej macierzy:
Aby dowiedzieć się, ile krawędzi łączy wierzchołki , wystarczy sprawdzić wartość komórki . Tak zaimplementowana komputerowa struktura danych gwarantuje, że operacje sprawdzenia, czy dodania oraz usunięcia krawędzi odbywają się w stałym czasie. Do jej wad należy duża ilość potrzebnej pamięci – O(n2), oraz fakt, że czas potrzebny do przejrzenia zbioru krawędzi jest proporcjonalny do kwadratu liczby wierzchołków (złożoność obliczeniowa wynosi O(n2), zamiast do liczby krawędzi.
• Lista sąsiedztwa
Drugą popularną reprezentacją grafu są tzw. listy sąsiedztwa – dla każdego wierzchołka zapamiętywana jest lista sąsiadujących z nim wierzchołków, np.:
W implementacji tej metody stosuje się listy jednokierunkowe oraz jednowymiarową tablicę wskaźników o rozmiarze | V(G) | , gdzie i-ty element tablicy jest wskaźnikiem do początku listy przechowującej sąsiadów i-tego wierzchołka. W odróżnieniu od macierzy sąsiedztwa, lista sąsiedztwa wymaga ilości pamięci proporcjonalnej do liczby krawędzi, także przejrzenie całego zbioru krawędzi jest proporcjonalne do jego rozmiaru. W stosunku do macierzy sąsiedztwa większą złożoność mają jednak operacje elementarne – sprawdzenie, czy wymaga czasu proporcjonalnego do mniejszego ze stopni wierzchołków, a np. usunięcie krawędzi – do większego z nich.
• Macierz incydencji
Macierz incydencji M wymiaru na zawiera informacje takie, że M(i,j) = 1 tylko, gdy j-ta krawędź kończy się w i-tym wierzchołku (czyli jest z nim incydentna). W przeciwnym wypadku M(i,j) = 0 Niech
oznaczają wszystkie krawędzie grafu z przykładu. Macierz incydencji o kolumnach e(i) i wierszach v(i) może wyglądać tak: