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, zbiorem wierzchołków, a zbiorem krawędzi.
Bez straty ogólności możemy nadać każdemu wierzchołkowi indeks Zbiór wierzchołków
Sam wierzchołek najlepiej reprezentować za pomocą rekordu, klasy lub innych struktur danych. Jeżeli miałby reprezentować strukturę pracowników firmy, definicja wierzchołka (pracownika) mogłaby wyglądać tak:
class CVertex { char Imie ; char Nazwisko ; double DochodNaDzien;
Reprezentacja przez macierz sąsiedztwa Macierz sąsiedztwa to dwuwymiarowa macierz, reprezentowana przez tablicę M o wymiarach na gdzie to liczba wierzchołków grafu. Jeżeli pomiędzy wierzchołkami i jest krawędź to w przeciwnym wypadku
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