Na początek kilka definicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane:

Rys.1. Graf nieskierowany	Rys.2. Graf skierowany

Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna.
Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.
Istnieje kilka algorytmów do przechowania grafu w pamięci.
Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:

	1	2	3	4	5
1	0	1	1	0	1
2	1	0	1	1	1
3	1	1	0	1	0
4	0	1	1	0	1
5	1	1	0	1	0

Złożoność pamięciowa

O(V2)

Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć rozmiar macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną.
Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:
1: 2, 3, 5
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3, 5
5: 4, 1    

Złożoność pamięciowa

O(V+E)

Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:

• 1 - 2
• 2 - 4
• 2 - 5
• 3 - 1
• 3 - 2
• 4 - 3
• 5 - 1
• 5 - 4

Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędź dwukrotnie: u - v oraz v - u.

Złożoność pamięciowa

O(E)

Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2.
Oto przykład dla grafu z rys. 2.

	1	2	3	4	5
1 - 2	-1	1	0	0	0
1 - 3	1	0	-1	0	0
1 - 5	1	0	0	0	-1
2 - 4	0	-1	0	1	0
2 - 5	0	-1	0	0	1
2 - 3	0	1	-1	0	0
3 - 4	0	0	1	-1	0
5 - 1	1	0	0	0	-1
5 - 4	0	0	0	1	-1

Złożoność pamięciowa

O(E*V)

Macierz grafu została opracowana w Instytucie Informatyki PP przez dr M. Sternę. Jest to trochę bardziej skomplikowana reprezentacja grafu niż poprzednie.
Należy utworzyć tablicę o rozmiarach (V+2)². Wiersze i kolumny numerujemy od 0 do V+1. Najpierw zajmiemy się częścią macierzy ograniczoną przez indeksy od 1 do V.Zał. że w wierszach mamy i-te wierzchołki a w kolumnach j-te wierzchołki. Liczby, które mogą znaleźć się na skrzyżowaniu wierzchołka i oraz j można podzielić na 3 grupy:

• od 1 do V - istnieje krawędź skierowana: i <- j
• od V+1 do 2*V - istnieje krawędź skierowana: i -> j
• od (-V) do (-1) - brak incydentnych krawędzi

Cały sekret macierzy grafu polega jednak na tym, że odczytana wartość nie tylko informuje nas, czy istnieje krawędź łącząca wierzchołki i oraz j, ale zawiera też adres następnego wierzchołka, który jest w takiej samej relacji z wierzchołkiem i co wierzchołek j.
Podam teraz kilka przykładów dla grafu z rys. 2. Liczba wierzchołków jest równa 5. Prześledzimy sytuację dla wierzchołka 1. w grafie mamy następujące krawędzie zawierające ten wierzchołek:

• 1 -> 2
• 1 <- 3
• 1 <- 5

Weźmy pierwszą krawędź: wierzchołek 2 jest jedynym następnikiem wierzchołka 1, więc w macierzy w komórce [1,2] musimy podać adres wierzchołka 2. Aby obliczyć adres wierzchołka nr. 2 (mamy do czynienia z następnikiem) wystarczy dodać do niego liczbę wierzchołków w grafie: 2+5=7. Taką liczbę zapisujemy w komórce [1,2].
Przejdźmy do krawędzi drugiej: wierzchołek 3 jest poprzednikiem wierzchołka 1, ale (w przeciwieństwie do następników) nie jedynym: także wierzchołek 5 jest poprzednikiem wierzchołka 1 (ostatnia krawędź na naszej liście). W komórce [1,3] musimy więc podać adres wierzchołka 5. Ponieważ jest to poprzednik, więc adresem wierzchołka 5 jest 5.
Przechodzimy do ostatniej krawędzi: wierzchołek 5 jest poprzednikiem wierzchołka, ponieważ jest jego ostatnim poprzednikiem (pierwszym był wierzchołek 3) w komórce [1,5] podajemy adres wierzchołka 5, czyli znów wpisujemy 5.
W naszej macierzy musimy podać także wierzchołki, które nie są połączone z wierzchołkiem 1 krawędzią. Punktem wyjściowym listy tych wierzchołków dla każdego wierzchołka i jest on sam (stąd: macierz grafu nie nadaje się dla grafów z pętlami własnymi), lista ta zaczyna się więc w komórce [i,i]. A więc wiemy, że wierzchołek 1 nie jest połączony krawędzią ze sobą samym oraz wierzchołkiem 4. W komórce [1,1] musimy podać adres wierzchołka 4, z godnie z tyum co napisałem powyżej, adresy wierzchołków, które nie są połączone z danym wierzchołek podaje się poprzedzając numer wierzchołka znakiem "-". Więc w komórce [1,1] piszemy (-4). Jednocześnie wierzchołek 4 jest ostatnim wierzchołkiem, z którym nie łączy się wierzchołek 1, więc w komórce [1,4] podajemy znów adres wierzchołka 4, czyli [1,4]=(-4).
Teraz zajmiemy się pozostałą częścią macierzy: kolumną nr. 0 i (V+1) oraz wierszem nr. 0 i (V+1). Bez nich można by już zapisać graf za pomocą macierzy, lecz dzięki nim będziemy mieli dostęp do listy poprzedników i następników w czasie O(E). A więc: komórka [i,0] zawiera pierwszy poprzednik wierzchołka i-tego natomiast komórka [0,i] ostatni poprzednik.
W przykładzie (dotyczącym wierzchołka 1) zapiszemy [1,0]=3, [0,1]=5, ponieważ pierwszym poprzednikiem wierzchołka 1 jest 3 a ostatnim poprzednikiem tego wierzchołka jest 5. Podobnie jest z następnikami: [i,V+1] rozpoczyna listę następników wierzchołka i-tego a [V+1,i] kończy, a więc [1,6]=2, [6,1]=2, gdyż pierwszym i ostatnim następnikiem wierzchołka 1 jest 2. W ten sposób wypełniliśmy pierwszy wiersz macierzy grafu.
Dodam jeszcze, że jeżeli jakiś wierzchołek nie ma następników lub poprzedników to na początku i końcu listy odpowiednio: następników lub poprzedników wpisujemy 0. Poniżej zamieszczam całą macierz dla grafu z rys. 2 (w kolumnach znajdują się wierzchołki j, w wierszach wierzchołki i).

	0	1	2	3	4	5	6
0	X	5	3	4	5	2	X
1	3	-4	7	5	-4	5	2
2	1	3	-2	3	10	10	4
3	4	7	7	-5	4	-5	1
4	2	-1	5	8	-1	5	3
5	2	9	2	-3	9	-3	1
6	X	2	5	2	3	4	X

Dla lepszego zrozumienia macierzy grafu proponuję narysować graf na podstawie macierzy i sprawdzić, czy jest to graf z rys. 2.

Dzięki dodatkowym kolumnom i wierszom zyskujemy listy następników i poprzedników:

• w kolumnie 0: wskaźnik do pierwszego elementu na liście poprzedników
• w wierszu 0: wskaźnik do ostatniego elementu na liście poprzedników
• w kolumnie V+1: wskaźnik do pierwszego elementu na liście następników
• w wierszu V+1: wskaźnik do ostatniego elementu na liście następników
• na głównej przekątnej: wskaźnik do pierwszego elementu na liście elementów nie będących ani następnikami ani poprzednikami

Złożoność pamięciowa

O((V+2)2)