Матрица смежности
Матрица смежности Sm - это квадратная матрица размером NxN (N - количество вершин в графе), заполненная единицами и нулями по следующему правилу:
Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = 1, в противном случае Sm[u,v] = 0.
Заметим, что данное определение подходит как ориентированным, так и неориентированным графам: матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа - несимметричной.
Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:
Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = ves(e), в противном случае Sm[u,v] = 0.
Это хорошо согласуется с замечанием, сделанным в предыдущем пункте: невзвешенный граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.
Небольшое затруднение возникнет в том случае, если в графе разрешаются ребра с весом 0. Тогда придется хранить два массива: один с нулями и единицами, которые служат показателем наличия ребер, а второй - с весами этих ребер.
В качестве примера приведем матрицы смежности для трех графов, изображенных на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.8).
| 0 | 1 | 1 | 0 | 0 | 10 | 1 | 0 | 1 | 0 | a0 | 1 | 10 | 0 |
| 1 | 0 | 1 | 1 | 1 | 20 | 0 | 0 | 0 | 0 | b1 | 0 | 2 | 10 |
| 1 | 1 | 0 | 1 | 1 | 31 | 1 | 0 | 0 | 1 | c10 | 2 | 0 | 3 |
| 0 | 1 | 1 | 0 | 1 | 40 | 0 | 1 | 0 | 0 | d0 | 10 | 3 | 0 |
| 0 | 1 | 1 | 1 | 0 | 50 | 0 | 0 | 0 | 0 |
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.
on_load_lecture()
Дальше »
Если Вы заметили ошибку - сообщите нам.
