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

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

Рисунок 3.6 – Матрица смежности

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

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

Рисунок 3.7 – Граф и его матрица смежности

Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 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 | ²) памяти, поскольку ее размер, как уже отмечалось, равен квадрату числа всех вершин. И если количество ребер графа, в сопоставлении с количеством вершин, невелико, то значения многих элементов матрицы смежности будут нулевыми, следовательно, использование данного метода нецелесообразно, т. к. для подобных графов имеются наиболее оптимальные способы их представления.