4.1.4. Представление графа в виде списка дуг

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

Рис.3. Граф и его представление в виде списка дуг

В листинге приведено представление графа в виде списка дуг. Такое представление будем называть A-графом от слова Arc— дуга. Список дуг представлен списком элементов, каждый из которых содержит два целых числа— номера концов дуги. В данной реализации список не представлен в виде отдельного описания класса. Вместо этого описание элемента такого списка— дуги— внесено прямо в описание класса для представления A-графа, а реализации операций над списком просто являются частью реализации операций над дугами графа.

Операция добавления дуги в этом представлении — это просто операция добавления одного элемента в конец списка, и реализуется она сравнительно эффективно. Напротив, при выполнении операции поиска дуги может потребоваться просмотреть весь список. Разумеется, настолько же неэффективной будет и операция удаления дуги.

файл ArcGraph.h

#include "graph.h" // Определение родительского класса

// Описание класса для представления A-графа

class ArcGraph : public Graph {

// Дуга представлена элементом списка, содержащим номера

// концов дуги и указатель на следующий элемент списка

struct Arc {

int begin, end;

Arc *next;

// Конструктор дуги.

Arc{int b, int e, Arc *n = NULL) {

begin = b; end = e; next = n; )

};

// Список дуг представлен, как обычно,

// указателями на первый и последний элементы списка

Arc *first, *last;

// arcCount - счетчик числа дуг-элементов списка

int arcCount;

// vertexNumber - количество вершин графа, используемое

//в данном представлении только для контроля номеров вершин

int vertexNumber;

public:

// Конструктор графа инициализирует пустой список

// и запоминает количество вершин графа.

ArcGraph(int n) {

first = last = NULL; arcCount = 0; vertexNumber = n;

}

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

int vertexCoun() const { return vertexNumber; }

// Операции над дугами:

void addArc(int from, int to);

bool hasArc(int from, int to) const;

};

файл ArcGraph.cpp

«include "ArcGraph.h"

//Реализация операции добавления дуги

void ArcGraph::addArc(int from, int to) {

// Сначала проверяем правильность задания номеров вершин.

if (from < 0 || to < 0 || from >= vertexNumber || to >=vertexNumber)

return;

Arc *newArc = new Arc(from, to);

// Новая дуга добавляется в конец списка

if (last) last->next = newArc; else first = newArc;

last = newArc;

arcCount++;

}

// Реализация операции проверки наличия дуги.

bool ArcGraph::hasArc(int from, int to) const {

// Необходимо просмотреть список дуг в поисках нужной.

for (Arc *current = first; current; current = current->next) {

if (current->begin == from && current->end == to)

return true;

}

return false;

}

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

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