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

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

${\displaystyle 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 ${\displaystyle 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;
};

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

Własności reprezentacji:

Macierz sąsiedztwa:

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

Zapamiętanie tablicy o rozmiarze ${\displaystyle 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ę ${\displaystyle LS.}$

Dla każdej krawędzi ${\displaystyle (v_{i},v_{j}),}$ do listy wskazywanej przez ${\displaystyle LS[i]}$ dodaje się indeks wierzchołka ${\displaystyle v_{j}.}$

${\displaystyle LS[i]}$ wskazuje teraz na listę zawierającą indeksy wszystkich sąsiadów wierzchołka ${\displaystyle v_{i}.}$

Aby usunąć krawędź ${\displaystyle (v_{i},v_{j})}$ wystarczy usunąć z listy ${\displaystyle LS[i]}$ indeks ${\displaystyle v_{j},}$ a z ${\displaystyle LS[j]}$ indeks ${\displaystyle 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: ${\displaystyle O(|V|+|E|)}$
• Dodanie nowej krawędzi: czas stały
• Sprawdzenie czy dana krawędź istnieje: ${\displaystyle O(|E|)}$
• Sprawdzenie stopnia danego wierzchołka: ${\displaystyle O(|E|)}$
• Usunięcie krawędzi: ${\displaystyle O(|E|)}$

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

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

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 ${\displaystyle V}$ wierzchołkach i ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle v}$ realizujemy przez zsumowanie wartości ${\displaystyle \mathrm {GMatrix} [v][i],}$ ${\displaystyle i\in 0,1,\dots n,}$ tj. liczby krawędzi o końcu w wierzchołku ${\displaystyle v.}$ Jeżeli obsługujemy graf skierowany funkcja ${\displaystyle \mathrm {Degree} (v)}$ zwróci liczbę krawędzi wychodzących z ${\displaystyle 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;
}

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 ${\displaystyle 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 ${\displaystyle \mathrm {Search} (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 ${\displaystyle \mathrm {Delete} (v,u)}$ wywołuje funkcję ${\displaystyle \mathrm {Search} (v,u),}$ która w przypadku istnienia krawędzi ${\displaystyle (v,u)}$ zapamiętuje wskaźniki odpowiednio na poprzedni i następny węzeł na liście. Jeżeli krawędź nie istnieje, ${\displaystyle \mathrm {Delete} }$ zwraca ${\displaystyle 0.}$ Jeżeli istnieje, węzeł ${\displaystyle u}$ jest usuwany z listy sąsiadów ${\displaystyle v,}$ i odwrotnie.