Sposoby reprezentacji grafów

Mirosław Mortka

Istnieją różne sposoby reprezentacji grafów. Zwrócimy uwagę na dwie najbardziej użyteczne.

Macierz sąsiedztwa (tablica sąsiedztwa)

Graf o $n$ wierzchołkach możemy reprezentować za pomocą tablicy $A$ o rozmiarze $n$ na $n$ elementów. Zapalona jedynka na pozycji $A[i][j]$ oznacza wówczas istnienie krawędzi między wierzchołkami $i$ oraz $j$. Zaletą takiego sposoby reprezentacji grafu jest możliwość natychmiastowego sprawdzenia istnienia krawędzi między dwoma wierzchołkami. Podobnie szybko możemy dodawać lub usuwać dowolne krawędzie. Wadą tej metody zapisu jest je złożoność pamięciowa - wymaga użycia tablicy o rozmiarze $n^2$. W przypadku grafów rzadkich (tj. takich, w których jest mało krawędzi w stosunku do liczby wierzchołków), większość pamięci przechowuje bezużyteczne informacje.

Listy sąsiedztwa

Grafy rzadkie można reprezentować za pomocą list sąsiedztwa. Wówczas dla każdego wierzchołka przechowujemy wyłącznie informacje o wierzchołkach będących jego sąsiadami. Zmniejsza to złożoność pamięciową dla grafu złożonego z $n$ wierzchołków i $k$ krawędzi do $O(n+k)$. Jednak aby stwierdzić występowanie krawędzi między wierzchołkami $i$ oraz $j$, musimy przeszukać całą listę sąsiadów wierzchołka $i$.

Przykłady implementacji grafów w C++

Załóżmy, że dla grafu pokazanego na poniższym rysunku przygotowanego zestaw danych, w którym w pierwszej linii znajdują się wie liczby całkowite n i k (liczba wierzchołków oraz liczba krawędzi). W następnych k liniach znajdują się opisy krawędzi w postaci dwóch liczb całkowitych u i v (numery wierzchołków, pomiędzy którymi istnieją krawędzie).

Przykładowe dane:
6 6
1 2
1 3
1 5
3 4
5 4
5 6

//deklaracja tablicy złożonej z N_MAX wektorów
//na i-tej pozycji przechowuję w wektorze listę sąsiadów i-tego wierzchołka
vector <int> A[N_MAX]
//liczba wierzchołków n oraz liczba krawędzi k
int n, k;
cin >> n >> k;
//k-krotnie wczytuję krawędzie
for (int i=0; i<k; i++) {
  int u, v; //numery wczytywanych wierzchołków
  cin >> u >> v;
  //dla wierzchołka u dodaję sąsaida v
  A[u].push_back(v);
  //w przypadku grafów nieskierowanych konieczne jest dodanie krawędzi powrotnej (v, u)
  A[v].push_back(u);
}

//przykładowe wypisanie grafu
//dla każdego z n wierzchołków
for (int i=1; i<=n; i++) { 
  cout << i << ": ";
  //wypisz wszystkich sąsiadów wierzchołka i
  for (int j=0; j<A[i].size(); j++)
    //wypisz j-tego sąsiada wierzchołka o numerze i
    cout << A[i][j] << " ";
  cout << endl;
}