Reprezentacja grafu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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, V zbiorem wierzchołków, a E zbiorem krawędzi.

Bez straty ogólności możemy nadać każdemu wierzchołkowi indeks Zbiór wierzchołków G:

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]

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 i 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:
  • 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ę LS.

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

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

Aby usunąć krawędź wystarczy usunąć z listy LS[i] indeks , a z LS[j] 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 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:
  • 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 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], , 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]

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.