Имеется два стандартных способа представления графа G = (V,E): как набора списков смежных вершин или как матрицы смежности. Оба способа применимы как для ориентированных, так и для неориентированных графов.

Представление с помощью списка смежности обеспечивает более компактное представление разреженных графов
(у которых |E| много меньше |V|^2). Представление при помощи матрицы смежности предпочтительнее в случае
плотных графов (когда |E| близко |V|^2) или когда необходима возможность быстро определить, имеется ребро,
соединяющее две данных вершины.

Например:

Представление в виде списка смежности для приведенного примера выглядит следующим образом:
1 | -> 2 -> 5
2 | -> 1 -> 3 -> 4 -> 5
3 | -> 2 -> 4
4 | -> 2 -> 3 -> 5
5 | -> 1 -> 2 -> 4

Представление графа массив |V| списков, по одному для каждой вершины. Для каждой вершины u из V список содержит все вершины v, такие что (u, v) принадлежат Е, т.е. список состоит из всех вершин, смежных с u. Вершины в каждом списке обычно хранятся в произвольном порядке. Как для ориентированных, так и для неориентированных графов представление в виде списков требует объем памяти, равный O(V + E).

Представление в виде матрицы смежности:
—————-
| 0 1 0 0 1 |
| 1 0 1 1 1 |
| 0 1 0 1 0 |
| 0 1 1 0 1 |
| 1 1 0 1 0 |
—————–

Предполагается, что вершины пронумерованы в некотором порядке 1, 2, …, |V|. В таком случае представление графа представляет собой матрицу размером |V| x |V|, такую что:

A[i][j] = 1 - если есть ребро от i до j (или наоборот, если граф неориентированный).
A[i][j] = 0 - в противном случае.