Reprezentacja grafu

Reprezentacja grafu to sposób zapisu grafu umożliwiający jego obróbkę z użyciem programów komputerowych. Dwa najpopularniejsze sposoby zapisu informatycznego grafów to macierz sąsiedztwa oraz listy sąsiedztwa.

Niech będzie grafem, zbiorem wierzchołków, a zbiorem krawędzi.

Bez straty ogólności możemy nadać każdemu wierzchołkowi indeks Zbiór wierzchołków

Sam wierzchołek najlepiej reprezentować za pomocą rekordu, klasy lub innych struktur danych. Jeżeli miałby reprezentować strukturę pracowników firmy, definicja wierzchołka (pracownika) mogłaby wyglądać tak:

Macierz sąsiedztwa to dwuwymiarowa macierz, reprezentowana przez tablicę M o wymiarach na gdzie to liczba wierzchołków grafu. Jeżeli pomiędzy wierzchołkami i jest krawędź to w przeciwnym wypadku

Własności reprezentacji:

Macierz sąsiedztwa:

  • Wymagania pamięciowe:
  • Dodanie nowej krawędzi: czas stały
  • Sprawdzenie czy dana krawędź istnieje: czas stały
  • Sprawdzenie stopnia danego wierzchołka:
  • Usunięcie krawędzi: czas stały

Zapamiętanie tablicy o rozmiarze jest dość kosztowne, zwłaszcza gdy bada się grafy rzadkie, tj. grafy o niewielkiej liczbie krawędzi w stosunku do grafu pełnego złożonego z tej samej liczby wierzchołków. W praktyce lista sąsiedztwa często okazuje się najefektywniejszą reprezentacją grafu.

Korzysta się z list – struktur danych, które przechowują różne wartości w komórkach zwanych węzłami. Tutaj w listach będziemy trzymać numery indeksów.

Tworzy się tablicę o rozmiarze równym liczbie wierzchołków, zawierającą wskaźniki na (początkowo puste) listy – kolejne elementy list oznaczać będą kolejnych sąsiadów danego wierzchołka, do którego lista jest przyporządkowana. Niech tablica nazywa się

Dla każdej krawędzi do listy wskazywanej przez dodaje się indeks wierzchołka

wskazuje teraz na listę zawierającą indeksy wszystkich sąsiadów wierzchołka

Aby usunąć krawędź wystarczy usunąć z listy indeks a z indeks

W przypadku grafów skierowanych stosuje się listy następników lub listy poprzedników – odpowiednio w tym wypadku zamiast dodawać sąsiadów, dodajemy do listy związanej z danym wierzchołkiem informacje o wierzchołkach, do których krawędź „wychodzi” lub z których krawędź „wchodzi” z tego, danego wierzchołka.

  • Wymagania pamięciowe:
  • Dodanie nowej krawędzi: czas stały
  • Sprawdzenie czy dana krawędź istnieje:
  • Sprawdzenie stopnia danego wierzchołka:
  • Usunięcie krawędzi:

Jeżeli w trakcie działania algorytmu teoriografowego graf nie ulega zmianie, to możemy zrezygnować ze wskaźników i zapamiętać wszystkie krawędzie po kolei w jednym wektorze. Uporządkowany zbiór wszystkich sąsiadów wierzchołka i nosi nazwę pęków wyjściowych (ang. forward star) tego wierzchołka i stąd nazwa tej struktury. Dla każdego sąsiedzi wierzchołka i są umieszczeni bezpośrednio za wierzchołkami-sąsiadami wierzchołka

Taka struktura wykorzystuje więc dwie tablice, pierwsza długości (nazwijmy ją Pntr), której numery indeksu odpowiadają kolejnym wierzchołkom grafu, a wartości pod indeksem -tym i wskazują odpowiednio na początek i koniec fragmentu drugiej tablicy (nazwijmy ją EndVertex), w którym są wymienieni sąsiedzi wierzchołka -tego (dzięki temu można wyliczyć stopień wierzchołka w czasie stały odejmując po prostu wartości w tablicy pod indeksem i oraz i+1 (stopień wierzchołka i = Pntr[i]-Pntr[i+1])).

Krawędzie wychodzące z wierzchołka nr i to po prostu: {i, Endvertex[Pntr[i]]}, {i, Endvertex[Pntr[i]+1]}, ..., {i, Endvertex[Pntr[i+1]-1]}. Przypadek i=n może być rozwiązany za pomocą wartownika który wskazuje na adres |E|+1 w wektorze EndVertex.

Dla grafu nieskierowanego pęki wyjściowe wymagają (|V|+1) + 2|E| komórek pamięci (wierzchołki + wartownik + podwójnie zapisane krawędzie (graf nieskieowany)).

Przypadek grafów skierowanych w żaden sposób nie komplikuje struktury pęków wyjściowych, zmniejsza jedynie ilość zajmowanego miejsca – |V|+1 + |E|, gdyż krawędzie nie są powielane.

  • Wymagania pamięciowe:
  • Dodanie nowej krawędzi:
  • Sprawdzenie czy dana krawędź istnieje:
  • Sprawdzenie stopnia danego wierzchołka:
  • Usunięcie krawędzi:

Realizacja obsługi grafu poprzez macierz jest dość prosta:

Konstruktor rezerwuje pamięć na macierz sąsiedztwa i tworzy graf o wierzchołkach i krawędziach. Destruktor zwalnia pamięć.

Dodanie krawędzi, jeżeli graf jest prosty i krawędź już istnieje funkcja zwraca Jeżeli graf nie jest skierowany symetryczna krawędź jest dodana.

Aby usunąć krawędź, należy sprawdzić czy takowa istnieje i w przypadku grafu prostego usunąć krawędź symetryczną.

Zliczanie sąsiadów wierzchołka realizujemy przez zsumowanie wartości tj. liczby krawędzi o końcu w wierzchołku Jeżeli obsługujemy graf skierowany funkcja zwróci liczbę krawędzi wychodzących z

Definicja klasy CGraph jest niemal taka sama:

Konstruktor rezerwuje pamięć na elementową tablicę wskaźników na listy, oraz ustawia początkowe zawartości list na NULL (graf bez krawędzi).

Funkcja przechodzi całą listę sąsiadów do napotkania węzła reprezentującego wierzchołek u, lub do końca listy, tj. węzła, którego wskaźnik next wskazuje na NULL;

Funkcja wywołuje funkcję która w przypadku istnienia krawędzi zapamiętuje wskaźniki odpowiednio na poprzedni i następny węzeł na liście. Jeżeli krawędź nie istnieje, zwraca Jeżeli istnieje, węzeł jest usuwany z listy sąsiadów i odwrotnie.

Copyright