Курсовая работа: Алгоритмы поиска остовного дерева Прима и Крускала

1 QV[G]

2 for для каждой вершины uQ

3 do key[u]

4 key[r] 0

5 [r] nil

6 while Q

7do u Extract-Min(Q)

8for для каждой вершины vAdj[u]

9 do if vQ и w(u,v)<key[v]

10 then [v] u

11 key(v) w(u,v)

После исполнения строк 1-5 и первого прохода цикла в строках 6 ‑ 11 дерево состоит из единственной вершины r, все остальные вершины находятся в очереди, и значение key[v] для них равно длине ребра из r в vили , если такого ребра нет (в первом случае [v] = r). Таким образом, выполнен описанный выше инвариант (дерево есть часть некоторого остова, для вершин дерева поле указывает на родителя, а для остальных вершин на "ближайшую" вершину дерева — вес ребра до неё хранится в key[v].

Время работы алгоритма Прима зависит от того, как реализована очередь Q. Если использовать двоичную кучу (7), инициализацию в строках 1-4 можно выполнить с помощью процедуры Build-Heapза время O(V). Далее цикл выполняется \V\ раз, и каждая операция Extract-Minзанимает время O(logV), всего O(VlogV). Цикл for в строках 8-11 выполняется в общей сложности О(Е) раз, поскольку сумма степеней вершин графа равна 2\Е\. Проверку принадлежности в строке 9 внутри цикла for можно реализовать за время O(1), если хранить состояние очереди ещё и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (Decrease-Key), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом, всего получаем O(VlogV+ ElogV) = O(ElogV) — та же самая оценка, что была для алгоритма Крускала.

Однако эта оценка может быть улучшена, если использовать в алгоритме Прима фибоначчиевы кучи, с помощью неё можно выполнять операцию Extract-Minза учётное время O(logV), а операцию Decrease-Key— за (учётное) время O(1). (Нас интересует именно суммарное время выполнения последовательности операций, так что амортизированный анализ тут в самый раз.) Поэтому при использовании фибоначчиевых куч для реализации очереди время работы алгоритма Прима составит O(Е + VlogV).

Программная реализация

Реализуем вышеописанные алгоритмы на практике с помощьюDelphi 7.

Данный скрин является подтверждением выполненной работы.

Вывод

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

Для алгоритма Прима количество сравнений и присваиваний больше, так как нужно сортировать данные два раза (в алгоритме Крускала 1 раз).

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

Программный код

program Project1;

uses

Forms,

Unit1 in 'Unit1.pas' {Main},

Unit2 in 'Unit2.pas' {AboutBox};

{$R *.res}