Graf to struktura składająca się z węzłów i połączeń. Połączenia mogą być jedno- lub dwu-kierunkowe (zależnie od potrzeb danego algorytmu). Załóżmy że rozmawiamy o grafie w którym dwa węzły mogą być połączone lub nie. Czyli NIE obsługujemy sytuacji:
- pomiędzy tymi samymi dwoma węzłami może istnieć więcej niż jedno połączenie
- połączenia skierowane, gdzie czymś innym jest połączenie A > B, B < A czy A <> B
Taki graf można zapisać więc jako "kwadratową" macierz połączeń, gdzie długość boku to ilość węzłów. Przykładowo graf składający się z 5 węzłów A,B,C,D,E, gdzie istnieją połączenia A-B, A-D, C-E, C-D może być zapisany tak:
# A B C D E
A x 1 0 1 0
B 0 x 0 0 0
C 0 0 x 1 1
D 0 0 0 x 0
E 0 0 0 0 x
Taką macierz możesz zaimplementować jako dwuwymiarową tablicę. Tylko że ona marnuje dużo miejsca. Połowa powierzchni jest niewykorzystana (wystarczy zaznaczyć A-B, B-A jest tym samym). Jak w graf jest mało połączony to większość pól to będą zera.
Dlatego częściej tworzy się jednowymiarową tablicę sąsiedztwa. To też tablica dwuwymiarowa, ale prostsza. Zapisujemy w niej tylko informację o połączeniach:
{
{A, B},
{A, D},
{C, E},
{C, D}
}
W ten sposób oszczędzasz dużo miejsca w pamięci pomijając zera.