Во втором способе представления – матрице смежности, граф из количества вершин n представлен в виде таблицы с n-м количеством строк и n-м количеством столбцов ( матрица размерности n×n). Если между любой вершиной x и вершиной y есть ребро, то элемент ax,y будет равен 1, в противоположном случае − 0. Например, список смежности и матрица смежности для графа, представленного выше, будут такими:
Вершина | Список смежности |
0 | 1, 2, 4 |
1 | 0, 2, 3, 4 |
2 | 0, 1 |
3 | 1 |
4 | 0, 1 |
5 |
0 | 1 | 2 | 3 | 4 | 5 | |
0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 1 | 0 |
2 | 1 | 1 | 0 | 0 | 0 | 0 |
3 | 0 | 1 | 0 | 0 | 0 | 0 |
4 | 1 | 1 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 |
Для сохранения графов в памяти компьютера используют как эти, так и другие способы. Например, если список смежности данного графа в языке Python назовем adjacency_list, а количество его вершин num_vertices то:
adjacency_list = [[1, 2, 4],
[0, 2, 3, 4],
[0, 1],
[1],
[0, 1],
[],
]
num_vertices = len(adjacency_list)
Если для этого графа обозначить матрицу смежности как adjacency_matrix:
adjacency_matrix = [[0, 1, 1, 0, 1, 0],
[1, 0, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
]
num_vertices = len(adjacency_matrix)
Следует заметить, матрица смежности обыкновенного (не ориентированного) графа всегда симметрична относительно главной диагонали. Главная диагональ матрицы проходит от верхнего левого угла к нижнему правому.