4.1.1. Представление графа в виде массива

Первое из описываемых представлений графа основано на следующих соображениях. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины u, идентифицируется своим концом— номером вершины, в которую эта дуга входит. Таким образом, граф представляется массивом, в котором каждому номеру вершины и в диапазоне от 0 до N сопоставлено множество целых чисел — номеров вершин, в которые входят дуги, исходящие из выбранной вершины u. Описанное представление графа будем называть S-графом (от set— множество). Будем считать, что множество целых чисел в диапазоне от 0 до N представлено объектом класса Set. Тогда S-граф может быть описан следующим классом:

файл graph.h

class Graph

{

public:

// Функция addArc позволяет добавить к графу новую дугу,

// ведущую из вершины с номером from в вершину с номером to.

virtual void addArc (int from, int to) = 0;

// Функция has Arc проверяет, имеется ли в графе дуга, ведущая

//из вершины с номером from в вершину с номером to.

virtual bool hasArc(int from, int to) const = 0;

// Функция vertexCount выдает число вершин графа

virtual int vertexCount() const = 0;

};

файл setgraph.h

#include "graph.h"

#include "set.h" // Определение класса для работы с множествами

class SetGraph : public Graph {

Set **graph; // Массив множеств дуг

int vertexNumber; // Число вершин

public:

// Конструктор графа с n вершинами создает массив из пустых множеств

SetGraph(int n) : vertexNumber(n), graph(new Set*[n])

{ for (int i = 0; i < n; i++) { graph[i] = new Set(0,n); }

}

// Деструктор уничтожает массив множеств

~SetGraph();

// Функция подсчета числа вершин просто выдает

// ранее сохраненное значение

int vertexCount () const { return vertexNumber; }

// Основные методы работы с графом

void addArc(int from, int to);

bool hasArc(int from, int to) const;

};

Все виртуальные функции легко реализуются с помощью соответствующих операций над множествами. Так, принадлежность дуги (и, v) графу может быть легко реализована следующим образом:

bool SetGraph::hasArc(int u, int v) const {

if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)

return false; // Неправильно задана дуга

return graph[u]->has(v); }

Аналогично, добавление дуги к графу реализуется так:

void SetGraph::addArc(int u, int v) {

if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)

return; // Неправильно задана дуга

*graph[u] |= v; }

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

В данном представлении также легко и эффективно реализуется метод, позволяющий удалить дугу с заданными номерами инцидентных ей вершин. Несколько сложнее решается задача перебора дуг, инцидентных данной вершине. Например, для того чтобы определить количество дуг, выходящих из вершины с заданным номером, нужно иметь возможность определять количество элементов в множестве. Если считать, что класс set содержит метод card для подсчета числа элементов множества (мощности множества), то число выходящих из заданной вершины u дуг легко получить с помощью выражения graph[u] .card(), однако число входящих в заданную вершину дуг может быть получено только путем перебора всех вершин графа.