Reprezentacja grafu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Reprezentacja przez pęki wyjściowe (ang. forward star)[edytuj | edytuj kod]

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, ..., 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)[edytuj | edytuj kod]

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)[edytuj | edytuj kod]

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.