W implementacji tablicowej zakłada się, że graf jest reprezentowany przez tak zwaną macierz sąsiedztwa. W najczystszej postaci macierz sąsiedztwa jest macierzą kwadratową indeksowaną wierzchołkami grafu, której elementy przyjmują wartości 0 lub 1. Jedynka (1) na przecięciu \( i \)-tego wiersza i \( j \)-tej kolumny mówi, że w grafie jest krawędź o końcach w \( i \) oraz \( j \), zaś zero (0) oznacza, że takiej krawędzi nie ma. W przypadku, gdy krawędzie mają wagi, macierz sąsiedztwa można zmodyfikować w następujący sposób. Jeśli \( i-j \) jest krawędzią w grafie, to na przecięciu tej \( i \)-tego wiersza i \( j \)-tej kolumny wstawiamy wagę \( w(i-j) \). Gdy takiej krawędzi nie ma w grafie, to w to miejsce wstawiamy \( \infty \). W takim przypadku elementy macierzy traktujemy jako wagi bezpośrednich połączeń pomiędzy wierzchołkami w grafie. Żeby być w zgodzie z tą konwencją przyjmujemy, że na przekątnej macierzy sąsiedztwa zawsze stawiamy zera. Podsumowując, w implementacji tablicowej przyjmujemy, że graf jest reprezentowany przez macierz kwadratową \( A[1..n,1..n] \) taką,że
Głównymi zaletami tej reprezentacji są jej prostota i to, że łatwo sprawdzać w czasie stałym, czy dwa wierzchołki są połączone krawędzią w grafie. Wadą jest to, że niezależnie od rozmiaru grafu, rozmiar tej reprezentacji jest zawsze kwadratowy. Tyle też czasu zajmuje jej inicjacja. Nawet jeśli byśmy przyjęli, że taka reprezentacja jest z góry zadana, to okazuje się, że przy tej reprezentacji grafu algorytmy dla znakomitej większości naturalnych problemów grafowych działają w czasie \( \Omega(n^2) \). Nie jest to źle dla grafów gęstych, w których \( m=\Theta(n^2) \), ale gdy chcemy uzyskiwać szybsze algorytmy dla grafów rzadszych, w szczególności liniowe ze względu na rozmiar grafu, to musimy myśleć o innej ich reprezentacji. Taką reprezentacją jest reprezentacja listowa.