Reprezentacja grafu

Reprezentacja grafu

Reprezentacja grafu to sposób zapisu grafu, który umożliwia jego przetwarzanie w programach komputerowych. Dwa najpopularniejsze metody to macierz sąsiedztwa oraz lista sąsiedztwa. W matematyce graf składa się ze zbioru wierzchołków $V$ i zbioru krawędzi $E$. Wierzchołki mogą być reprezentowane przez różne struktury danych, na przykład klasy.

Reprezentacja przez macierz sąsiedztwa

Macierz sąsiedztwa to dwuwymiarowa tablica $M$ o wymiarach $[0dots\; V-1]$ na $[0dots\; V-1]$. Jeśli istnieje krawędź między wierzchołkami $v\_i$ i $v\_j$, to $M[i][j]=1$, w przeciwnym razie $M[i][j]=0$.

• Wymagania pamięciowe: $O(|V|^2)$
• Dodanie krawędzi: czas stały
• Sprawdzenie krawędzi: czas stały
• Sprawdzenie stopnia wierzchołka: $O(|V|)$
• Usunięcie krawędzi: czas stały

Reprezentacja przez listę sąsiedztwa

Lista sąsiedztwa jest efektywną reprezentacją, zwłaszcza dla grafów rzadkich. Wykorzystuje struktury danych w postaci list, które przechowują numery sąsiadów dla każdego wierzchołka.

• Wymagania pamięciowe: $O(|V|+|E|)$
• Dodanie krawędzi: czas stały
• Sprawdzenie krawędzi: $O(|E|)$
• Sprawdzenie stopnia wierzchołka: $O(|E|)$
• Usunięcie krawędzi: $O(|E|)$

Reprezentacja przez pęki wyjściowe

W przypadku niezmiennego grafu podczas działania algorytmu można użyć struktury pęków wyjściowych. W tej metodzie sąsiedzi są przechowywani w jednej tablicy, co umożliwia szybkie obliczenie stopnia wierzchołka.

• Wymagania pamięciowe: $O(|V|+|E|)$
• Dodanie krawędzi: $O(|V|+|E|)$
• Sprawdzenie krawędzi: $O(log|V|)$
• Sprawdzenie stopnia wierzchołka: $O(1)$
• Usunięcie krawędzi: $O(|V|+|E|)$

Implementacja grafu w C++

Implementacja grafu przy użyciu macierzy jest prosta. Poniżej przedstawiono przykładową klasę dla reprezentacji macierzowej.

class CGraph
{
unsigned V,E; // liczba wierzchołków i krawędzi
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. W przypadku reprezentacji listowej, klasa jest podobna, ale używa wskaźników do list sąsiadów.

• Implementacja reprezentacji listowej także wymaga rezerwacji pamięci na tablicę wskaźników oraz inicjalizacji list sąsiadów.

Obie implementacje pozwalają na dodawanie, usuwanie oraz sprawdzanie krawędzi w grafie.