Матрица смежности

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рис. 1).

Бинарная матрица

Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф.

matrix_smeghnost

Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.

Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.

В программе матрица смежности задается при помощи обычного двумерного массива, имеющего размерность n×n, где n – число вершин графа.

На языке C++, описать ее можно, например, так:

int graph[n][n] = {
{0, 1, 0, 1},
{0, 0, 1, 1},
{0, 1, 0, 0},
{1, 0, 1, 0}};

В Паскале способ описания практически аналогичен:

const graph: array[1..n,1..n] of integer = (
(0, 1, 0, 1),
(0, 0, 1, 1),
(0, 1, 0, 0),
(1, 0, 1, 0));

В случае если граф неизвестен заранее, а определяется пользователем, то нужно организовать ручной ввод двумерного массива, так как это предусматривает конкретный язык программирования.

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

Рейтинг
( 2 оценки, среднее 5 из 5 )
Загрузка ...