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:

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

Reprezentacja przez macierz sąsiedztwa

edytuj

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

Reprezentacja przez listę sąsiedztwa

edytuj

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:  

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

edytuj

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:  

Implementacja grafu w C++ (reprezentacja macierzowa)

edytuj

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   wierzchołkach i   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   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   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  

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)

edytuj

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   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   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   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.