Graf to struktura składająca się z wierzchołków (zbiór V) i krawędzi (zbiór E). W przypadku grafów skierowanych krawędzie nazywane są łukami.
Graf możemy reprezentować w pamieci poprzez:
- Macierz sąsiedztwa
- Wiersze i kolumny reprezentują poszczególne wierzchołki
- Jeżeli istnieje łuk między i-tym i j-tym wierzchołkiem, to G[i][j]=1
- Jeżeli istnieje krawędź między i-tym i j-tym wierzchołkiem, to G[i][j]=G[j][i]=1
- Macierz incydencji
- Wiersze reprezentują wierzchołki, kolumny reprezentują krawędzie
- k-ty łuk pomiędzy i-tym i j-tym wierzchołkiem oznaczony jest przez G[i][k]=1 i G[j][k]=−1
- k-ta krawędź pomiędzy i-tym i j-tym wierzchołkiem oznaczona jest przez G[i][k]=G[j][k]=1
- Lista krawędzi
- Lista par w formacie (i,j)(i,j) dla każdego połączenia między i-tym a j-tym wierzchołkiem
- W przypadku grafów nieskierowanych wystarczy podawać tylko takie pary (i,j)(i,j), dla których i<j
- Listy sąsiedztwa/incydencji
- Dotyczy tylko grafów nieskierowanych
- Dla każdego wierzchołka i utrzymywana jest osobna lista z indeksami wierzchołków połączonych z i krawędzią
- Listy następników i lista poprzedników
- Dotyczy tylko grafów skierowanych
- Dla każdego wierzchołka i utrzymywana jest lista z indeksami następników i oraz druga lista z indeksami poprzedników i