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 $G=<V,E>$ będzie grafem, $V$ zbiorem wierzchołków, a $E$ zbiorem krawędzi.

Bez straty ogólności możemy nadać każdemu wierzchołkowi indeks $i\in 0..|V|-1$ Zbiór wierzchołków $G:$

$v_0,v_1,v_2,\dots ,v_{|V|-1}.$

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

class CVertex
{
     char Imie[16] ;
     char Nazwisko[16] ;
     double DochodNaDzien;
};

Reprezentacja przez macierz sąsiedztwa

Macierz sąsiedztwa to dwuwymiarowa macierz, reprezentowana przez tablicę M o wymiarach $[0\dots V-1]$ na $[0\dots V-1],$ gdzie $V$ to liczba wierzchołków grafu. Jeżeli pomiędzy wierzchołkami $v_i$ i $v_j$ jest krawędź to $M[i][j]=1,$ w przeciwnym wypadku $M[i][j]=0.$

Własności reprezentacji:

Macierz sąsiedztwa:

• Wymagania pamięciowe: $O(|V{|}^2)$
• Dodanie nowej krawędzi: czas stały
• Sprawdzenie czy dana krawędź istnieje: czas stały
• Sprawdzenie stopnia danego wierzchołka: $O(|V|)$
• Usunięcie krawędzi: czas stały

Reprezentacja przez listę sąsiedztwa

Zapamiętanie tablicy o rozmiarze $V^2$ 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ę $LS.$

Dla każdej krawędzi $(v_i,v_j),$ do listy wskazywanej przez $LS[i]$ dodaje się indeks wierzchołka $v_j.$

$LS[i]$ wskazuje teraz na listę zawierającą indeksy wszystkich sąsiadów wierzchołka $v_i.$

Aby usunąć krawędź $(v_i,v_j)$ wystarczy usunąć z listy $LS[i]$ indeks $v_j,$ a z $LS[j]$ indeks $v_i.$

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: $O(|V|+|E|)$
• Dodanie nowej krawędzi: czas stały
• Sprawdzenie czy dana krawędź istnieje: $O(|E|)$
• Sprawdzenie stopnia danego wierzchołka: $O(|E|)$
• Usunięcie krawędzi: $O(|E|)$

Reprezentacja przez pęki wyjściowe (ang. forward star)

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 $i=2,\dots ,n$ sąsiedzi wierzchołka i są umieszczeni bezpośrednio za wierzchołkami-sąsiadami wierzchołka $i-1.$

Taka struktura wykorzystuje więc dwie tablice, pierwsza długości $|V|+1$ (nazwijmy ją Pntr), której numery indeksu odpowiadają kolejnym wierzchołkom grafu, a wartości pod indeksem $i$-tym i $i+1$ wskazują odpowiednio na początek i koniec fragmentu drugiej tablicy (nazwijmy ją EndVertex), w którym są wymienieni sąsiedzi wierzchołka $i$-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: $O(|V|+|E|)$
• Dodanie nowej krawędzi: $O(|V|+|E|)$
• Sprawdzenie czy dana krawędź istnieje: $O(log|V|)$
• Sprawdzenie stopnia danego wierzchołka: $O(1)$
• Usunięcie krawędzi: $O(|V|+|E|)$

Implementacja grafu w C++ (reprezentacja macierzowa)

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

class CGraph
{
    unsigned V,E;       // liczba wierzcholkow i krawedzi
    bool DiGraph;       // czy digraf?
    bool MultiGraph;      // czy multigraf?

    unsigned **GMatrix; // macierz

//*******************************************************//
    public:

    CGraph(unsigned _V, bool _di, bool _mu);
    ~CGraph();
    bool Insert(unsigned v,unsigned u);
    bool Delete(unsigned v,unsigned u);
    unsigned Degree(unsigned v);
    bool Search(unsigned v,unsigned u);
};

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

CGraph::CGraph(unsigned _V, bool _di, bool _mu) : V(_V), DiGraph(_di), MultiGraph(_mu)
    {
      GMatrix = new unsigned*[_V];
      for(int i=0;i<V;++i)
      {
          GMatrix[i]= new unsigned[V];
          for(int j=0;j<V;++j) GMatrix[i][j]=0;
      }
    }
CGraph::~CGraph()
{
    for(int i = 0; i < V; ++i)
         delete[] GMatrix[i];
    delete[] GMatrix;
}

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

bool CGraph::Insert(unsigned v,unsigned u)
{
    if(!MultiGraph && (GMatrix[v][u]>0)) return false; // już jest!
    ++GMatrix[v][u];
    if(!DiGraph) ++GMatrix[u][v];   // krawędź symetryczna
}

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

bool CGraph::Delete(unsigned v,unsigned u)
{
    if(GMatrix[v][u]==0) return false; // nie ma co usunąć!
    --GMatrix[v][u];
    if(!DiGraph) --GMatrix[u][v];
}

Zliczanie sąsiadów wierzchołka $v$ realizujemy przez zsumowanie wartości $\mathrm{G}\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}[v][i],$ $i\in 0,1,\dots n,$ tj. liczby krawędzi o końcu w wierzchołku $v.$ Jeżeli obsługujemy graf skierowany funkcja $\mathrm{D}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{e}(v)$ zwróci liczbę krawędzi wychodzących z $v.$

unsigned CGraph::Degree(unsigned v)
{
        unsigned Result=0;
        for(int i=0;i<V;++i) Result+=GMatrix[v][i];
        return Result;
}

bool CGraph::Search(unsigned v,unsigned u)
{
        if(GMatrix[v][u]>0) return true;
        else return false;
}

Implementacja grafu w C++ (reprezentacja listowa)

Definicja klasy CGraph jest niemal taka sama:

class CGraph
{
    unsigned V,E;       // liczba wierzcholkow i krawedzi
    bool DiGraph;       // czy digraf?
    bool MultiGraph;    // czy multigraf?

    node *vPrev,*vNext,*uPrev,*uNext;

    node **GLists;     // tablica wskazników na listy wierzchołków

//*******************************************************//
    public:

    CGraph(unsigned _V, bool _di, bool _mu);
    ~CGraph();
    bool Insert(unsigned v,unsigned u);
    bool Delete(unsigned v,unsigned u);
    unsigned Degree(unsigned v);
    bool Search(unsigned v,unsigned u);
};

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

CGraph::CGraph(unsigned _V, bool _di, bool _mu) : V(_V), DiGraph(_di), MultiGraph(_mu)
{
   GLists = new node*[V];
   for(int i=0;i<V;++i) GLists[i]=NULL;
}

Funkcja $\mathrm{S}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h}(v,u)$ 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;

bool CGraph::Search(unsigned v,unsigned u)
{
     node* hand;        //pomocnik

     hand=GLists[v] ;   //szuka wśród sąsiadów v
     while(hand!=NULL)  //dopóki nie sprawdzi wszystkich
     {
         if((*hand). Index()==u) //jest!
         {
            uPrev=(*hand). GetPrev();
            uNext=(*hand). GetNext();
            return true;
         }
         hand=(*hand). GetNext();
     }

     if(DiGraph) return false;

     hand=GLists[u] ;   //szuka wśród sąsiadów u
     while(hand!=NULL)  //dopóki nie sprawdzi wszystkich
     {
         if((*hand). Index()==v) //jest!
         {
            vPrev=(*hand). GetPrev();
            vNext=(*hand). GetNext();
            return true;
         }
         hand=(*hand). GetNext();
     }
     return false; //nie znalazł
}

Funkcja $\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}(v,u)$ wywołuje funkcję $\mathrm{S}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h}(v,u),$ która w przypadku istnienia krawędzi $(v,u)$ zapamiętuje wskaźniki odpowiednio na poprzedni i następny węzeł na liście. Jeżeli krawędź nie istnieje, $\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}$ zwraca $0.$ Jeżeli istnieje, węzeł $u$ jest usuwany z listy sąsiadów $v,$ i odwrotnie.