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

Пусть для графа ½V½= n, тогда матрица смежности имеет размерность n´n и элементы ее определяются следующим образом:

Для взвешенных графов элементы матрицы смежности определяются следующим образом:

Рассмотрим примеры матриц смежности:

для рис. 4.1

для рис. 4.2

для рис. 4.3

для рис. 4.4

Замечание. Матрица смежности для неориентированного графа является симметричной.

Недостатком этого представления является то, что матрица требует n² ячеек памяти и может быть сильно разрежена в случае, когда число ребер (дуг) много меньше, чем n². Достоинством является то, что матрица позволяет быстро определить, соединены ли две данные вершины ребром (дугой).

С этой матрицей достаточно просто работать, поэтому ее имеет смысл использовать для плотных графов (когда количество дуг сравнимо с n²) или когда граф небольшой и места в памяти достаточно.

На С++ матрицу смежности можно описать в виде обычного двумерного массива, например:

int ** mas; или int mas [n][n];

В последнем случае количество вершин в графе n должно быть определено до момента описания графа.

Дата добавления: 2014-12-16