#include "MatrixGraph.h"
// Реализация конструктора - заказ и инициализация памяти
// под двумерный массив логических значений
MatrixGraph::MatrixGraph(int n)
{
graph = new bool*[vertexNumber = n];
for (int i = 0; i < n; i++)
{
bool * row = graph[i] = new bool[n];
for (int j = 0; j < n; j++) {
row[j] = false; }
}
}
bool MatrixGraph::rhasArc(int from, int to) const
{
if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)
return false; // неправильно заданы номера вершин
return graph[from][to];
}
void MatrixGraph::addArc(int from, int to)
{
if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber)
return; // невозможно добавить дугу
graph[from][to] =true; )
Поскольку представление M-графа очень близко к представлению S-графа, то и операции над M-графом выполняются практически с той же степенью эффективности, что и для S-графа. Удобными и эффективно реализуемыми операциями над M-графом являются операции проверки наличия дуги, значения ее нагрузки (в случае нагруженного графа), добавления и удаления дуг, изменения нагрузки.
Менее эффективными операциями будут операция подсчета или перебора дуг, инцидентных заданной вершине. Между тем во многих алгоритмах именно эта операция является самой часто используемой. Структура графа может меняться крайне редко, а вот исследоваться эта структура будет достаточно часто, причем инцидентность вершин и дуг чаще всего является главным предметом таких исследований. В этом случае представление графа в виде матрицы смежности будет неудобным.
Еще одно соображение. Если число вершин графа велико, то матрица смежности будет занимать достаточно много места. В то же время в графе количество дуг чаще всего существенно меньше NxN— размера матрицы, так что большинство элементов матрицы смежности будут пустыми.