Файл listgraph.cpp

// Собственно алгоритм Крускала

double ListGraph::minSkeleton(

// Выходной поток для вывода результирующей информации:

std::ostream & out,

// Нагрузка на ребра графа:

const GraphWeight & gw) {

// Суммарный вес найденного минимального остовного дерева:

double weight = 0;

// Пирамида, содержащая информацию о ребрах графа:

ArrayHeap<Arc> arcs(vertexNumber * vertexNumber / 2);

 

// Структура узла в лесе, представляющем частично построенное

// минимальное остовное дерево

struct SkeletonNode {

int node; // номер узла исходного графа

int next; // ссылка на родительский узел

// Конструкторы:

SkeletonNode(int n = 0) : node(n), next(-l) {}

SkeletonNode(const SkeletonNode & node) : node(node.node), next(node.next) {}

};

// Начальное заполнение пирамиды ребер:

// просматриваются все ребра графа,

//и информация о них заносится в пирамиду,

for (int i = 0; i < vertexNumber; i++) {

Iterator<int> *neighbors = graph[i].iterator();

while (neighbors->hasMoreElements()) {

int j = **neighbors;

}

// Граф неориентированный, поэтому для исключения дублирования

// информации рассматриваются только дуги, ведущие из вершины

// с меньшим номером в вершину с большим номером. Петли

// (если они есть) сразу же исключаются,

if (i < j) {

// Добавление ребра в пирамиду:

arcs += Arc(i, j, gw.arcLength(i, j));

}

++*neighbors;

}

delete neighbors;

// Начальное заполнение леса: каждая вершина графа представляет

// собой отдельное дерево, состоящее из единственной вершины.

SkeletonNode skeleton[vertexNumber];

for (int i = 0; i < vertexNumber; i++) {

skeleton[i] = SkeletonNode(i);

}

// Основной цикл по ребрам, включенным в пирамиду

while (!arcs.empty()) {

// Очередное ребро берется с вершины пирамида и исключается из нее

Arc nextArc = *arcs;

arcs, remove ();

// u и v - концы выбранного ребра

int u = nextArc. from, v = nextArc.to;

// Следующие два цикла находят корни деревьев,

// содержащих эти вершины:

while(skeleton[u].next ! = -1) u = skeleton[u].next;

while(skeleton[v].next != -1) v = skeleton[v].next;

if (u != v) {

// Ребро включается в остовное дерево,...

out « nextArc « "; ";

weight += nextArc.weight;

// ... а два дерева соединяются в одно.

skeleton[u]-next = v;

}

return weight;

}

 

При попытке вычислить минимальное остовное дерево для графа, приведенное на рис. 9, с помощью вызова метода:

cout « testGraph.minSkeleton(cout, arcsWeight);

В стандартный выходной поток будет выведена следующая информация:

(2,5); (0,3); (5,8); (0,6); (0,1); (1,4); (4,7); 15

Что и свидетельствует о том, что минимальное остовное дерево построено правильно, поскольку содержит ребра (2, 5), (0, 3), (5, 8), (0, б), (0, 1), (1, 4), (4, 7) и суммарный вес всех ребер составляет минимально возможную величину 15.

Еще один алгоритм построения минимального остовного дерева напоминает алгоритм Дейкстры для поиска наименьшего пути между двумя вершинами в графе и носит название алгоритма Прима (R. С. Prim).

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

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

Если для графа, изображенного на рис. 9, начать поиск минимального остовного дерева с вершины 0, то к дереву будут последовательно присоединяться ребра 0—3 (длиной 1), 0—1 (2), 0—6 (2), 1—4 (3), 4—7 (4), вершина 2 (+∞), 2—5(1), 2—8 (2).

На рис. 11 показана последовательность построения минимального остовного дерева для графа, изображенного на рис. 9.

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

 

Листинг : Алгоритм Прима нахождения минимального остовного дерева

 

double ListGraph::minSkeletonPrim(

// Выходной поток для вывода результирующей информации:

std::ostream & out,

// Нагрузка на ребра графа:

const GraphWeight & gw) {

// Множество непройденных вершин (сначала - все вершины)

Set notPassed(0, vertexNumber-1);

notPassed.addScale(0, vertexNumber-1);

// Массив расстояний от вершин до уже построенной части

double *dist - new double[vertexNumber];

// Массив направлений от новых вершин к уже построенной части

double *ends = new double[vertexNumber];

// Инициализация массивов расстояний и направлений

for (int i = 0; i < vertexNumber; i++) {

dist[i] = INFINITY;

ends[i] = -1;

}

// Суммарный вес построенной части дерева

double sumWeight =0;

// Основной цикл поиска новых вершин

while (!notPassed.empty()) {

// Поиск ближайшей вершины

double minDist = INFINITY;

Iterator<int> *iVertices = notPassed.iterator();

int minVertex = **iVertices;

while (iVertices->hasMoreElements()) {

int nextVertex = **iVertices;

if (dist[nextVertex] < minDist) {

minDist = dist[nextVertex];

minVertex = nextVertex;

} ++*iVertices; }

delete iVertices;

if (dist[minVertex] < INFINITY) {

// Присоединяем очередное ребро

out << "(" << ends[minVertex] << "," << minVertex <<”);”;

sumWeight += minDist;

}

notPassed -= minVertex;

// Новая вершина присоединена;

// корректируем информацию о расстояниях

Iterator<int> *neighbors = graph[minVertex].iterator();

while (neighbors->hasMoreElements()) {

int next = **neighbors;

if (notPassed.has(next)&& gw.arcLength(minVertex, next) < dist[next]) {

dist[next] = gw.arcLength(minVertex, next);

ends[next] = minVertex;

} ++*neighbors;

} delete neighbors;

} return sumWeight;

}

 

Рис. 11. Этапы построения остовного дерева согласно алгоритму Прима

Если применить метод minSkeietonPrim к графу, изображенному на рис. 9

cout « testGraph.minSkeleton(cout, arcsWeight);

то, разумеется, результат будет примерно тем же самым, что и при применении метода minskeieton, реализующего жадный алгоритм:

(0,3); (0,1); (0,6); (1,4); (4,7); (2,5); (2,8); 15

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