«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;
}
Конечно, выбирать представление графа для решения конкретной задачи нужно исходя из того, какие операции с графами будут выполняться чаще всего. Если в процессе работы граф часто меняет структуру связей, то, наверное, лучшим способом представления будет матрица смежности. Если наиболее частой операцией будет поиск путей в графе, проходящих по направлению дуг, то более удобным и выгодным способом будет способ представления графа в виде списков смежности.
Однако иногда бывает, что выбрать какой-то один способ представления графа трудно, например, потому, что в разные периоды времени работы программы требуется выполнять различные операции. В этом случае было бы удобно переходить от одного представления графа к другому. К счастью, такие преобразования занимают не очень много времени. Конечно, для преобразования придется, по крайней мере, один раз просмотреть весь граф, но время, затраченное на построение нового представления, всегда будет прямо пропорционально размеру графа. Это означает, что если время работы некоторого алгоритма на графе имеет порядок сложности не меньше размера графа, то скорость его работы практически не зависит от способа представления графа, поскольку всегда можно перед началом работы выполнить нужное преобразование без существенной потери эффективности основного алгоритма.