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,\cdots,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...V-1] na [0...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(|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|)$

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 GMatrix[v][i], $i\in 0,1,\ldots n$, tj. liczby krawędzi o końcu w wierzchołku v. Jeżeli obsługujemy graf skierowany funkcja Degree(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 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 Delete(v,u) wywołuje funkcję Search(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, Delete zwraca 0. Jeżeli istnieje, węzeł u jest usuwany z listy sąsiadów v, i odwrotnie.