Представление графа в виде матрицы смежности

 

Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается информация о дугах, ведущих из вершины с номером i в вершину с номером j. В важном частном случае простого графа, т. е. графа, в котором каждая упорядоченная пара вершин соединена не более чем одной дугой, и отсутствуют дуги вида (u, u), элементы матрицы могут принимать значения 0 или 1 в зависимости от того, существует ли соответствующая дуга. Ясно, что такое представление самым тесным образом связано с представлением, описанным выше в определении класса setGraph.

Представление в виде матрицы смежности будем называть М-графом. Удобно связывать с матрицей смежности информацию о нагрузке на дуги. В этом случае элементом матрицы будет либо значение нагрузки на соответствующую дугу, либо некоторое стандартное значение, говорящее об отсутствии дуги.

Рис.1. граф и его представление в виде матрицы смежности

 

Если, например, граф моделирует транспортную сеть, в которой нагрузка на дугу представляет расстояние между пунктами, соединенными этой дугой, то признаком отсутствия дуги удобно сделать значение 0 или, напротив, максимально возможное целое, смотря по тому, что окажется более удобным в используемом алгоритме. В общем виде, если тип нагрузки представлен значениями класса W, то представление графа будет содержать двумерный массив значений класса W. Мы для простоты не будем интересоваться нагрузкой на дуги графа, таким образом, элементами матрицы, представляющей М-граф, могут быть просто логические значения.