2.2. Векторы смежности
 

При представлении графа в виде векторов смежности создается матрица, число строк которой равно числу вершин графа. Каждая i-я строка матрицы содержит номера вершин, смежных с i-той вершиной, петли исключаются. Число столбцов матрицы определяется максимальной полустепенью исхода в орграфе или максимальной степенью в неориентированном графе.

G1             G2
2 3 0          2 4 0 0 0
0 0 0          1 3 4 0 0
2 4 5          2 4 0 0 0
5 0 0          1 2 3 5 6
6 0 0          4 6 0 0 0
4 0 0          4 5 0 0 0
Представление векторов смежности массивами

Такие массивы занимают меньше памяти, время просмотра их сокращается. Однако и здесь не удается избежать разреженности матрицы, если полустепень исхода какой-либо отдельной вершины близка к числу вершин графа.