2. Алгоритм Прима

2.1 Краткое описание алгоритма

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

Алгоритм Прима:

1. Построение остовного дерева T начинается с произвольной вершины .

2. Среди ребер, инцидентных вершине , выбирается ребро наименьшего веса и включается в дерево T.

3. Повторяя процесс, выполняется поиск наименьшего по весу ребра, соединяющего вершины и u с некоторой другой вершиной графа.

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

Алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

Неформальное описание алгоритма:

• Выбрать корневую вершину V;

• Пометить V как посещенную;

• Для каждой смежной с V вершины установить затраты кратчайшего ребра;

• Выбрать не посещённую вершину с наименьшим весом ребра в качестве текущей вершины;

• V и добавить связывающее ребро в остовное дерево;

• Повторить все шаги со второго, пока не будут посещены все вершины.

На рисунке 1 представлена блок-схема алгоритма Прима.

---

Р
исунок 1 – Блок – схема алгоритма Прима

---

2.2Разработка псевдокода

Алгоритм Прима.

На рисунке 2 представлен псевдокод алгоритма Прима. На входе матрица смежности cost[i][j] размером n/n.

Рисунок 2 – Псевдокод реализации алгоритма Прима через матрицу смежностей

На выходе мы имеем минимальное остовное дерево N и суммарный вес каркаса mincost.

Алгоритм Крускала. На рисунке 3 представлен псевдокод алгоритма Крускала. На входе матрица смежности cost[i][j] размером n/n.

Рисунок 3 – Псевдокод реализации алгоритма Крускала через матрицу смежностей

На выходе мы имеем минимальное остовное дерево.

---

2.3 Визуализация алгоритма

Проиллюстрируем алгоритм Прима графе. На рисунке 1 представлен исходный звешенный связный неориентированный граф. Выберем вершину A в качестве начальной. Среди ребер, инцидентных вершине A, выбираем ребро A,D наименьшего веса и включаем его в остовное дерево T. Вершина D инцидентна ребрам (D,B), (D,E), (D,F). В остов включаем ребро (D,F). Ребро (A,B), имеет меньший вес чем ребро (F,E), с силу данного обстоятельства, нам необходимо вернуться в вершину A и включить в дерево ребро (A,B).Далее проходим по незадействованным вершинам и включаем в остов ребра (B,E), (E,C), (E,G). В результате мы получаем минимальное остовное дерево – рисунок 5.

Рисунок 4 – Исходный  взвешенный связный неориентированный граф.

Рисунок 5 – Минимально остовное дерево исходного графа.

---

3. Анализ трудоемкости

Анализ алгоритма Прима

Время выполнения программы, имеет порядок O(n).

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь Q реализована как обычный массив d, то Extract.Min(Q) выполняется за O(n), а стоимость операции d[u] ← w(v, u) составляет O(1). Если Q  представляет собой бинарную пирамиду, то стоимость Extract.Min(Q) снижается до O(logn), а стоимость d[u] ← w(v, u) возрастает до O(logn). При использовании фибоначчиевых пирамид операция Extract.Min(Q)  выполняется за O(logn),аd[u] ← w(v, u) за O(1). Что наглядно продемонстрированно в таблице 1.

Таблица 1 зависимость асимптотики от способа реализации алгоритма

Способ представления графа и приоритетной очереди	Асимптотика
Массив d, списки смежности (матрица смежности)	O(V2)
Бинарная пирамида, списки смежности	O((V+E) log V) = O(E log V)
Фибоначчиева пирамида, списки смежности	O(E+V log V)

4.Тестирование программ реализации алгоритмов

4.1 Тестирование правильности

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

Таблица 2 протокол тестирования правильности

№ п/п	Входные данные	Выходные данные				Тест
		Ожидаемый результат		Действительный результат
	Cost[4][4]	_mincost	МОД	_mincost	МОД
1	0 5 9 12 11 0 4 0 1 0 0 11 14 9 0 0	20	Ребро 1:(1 2) вес:5 Ребро 2:(2 3) вес:4 Ребро 3:(3 4) вес:11	20	Ребро 1:(1 2) вес:5 Ребро 2:(2 3) вес:4 Ребро 3:(3 4) вес:11	+
2	0 14 12 12 6 0 2 12 10 11 0 8 12 1 5 0	21	Ребро 1:(1 3) вес:12 Ребро 2:(3 4) вес:8 Ребро 3:(4 2) вес:1	21	Ребро 1:(1 3) вес:12 Ребро 2:(3 4) вес:8 Ребро 3:(4 2) вес:1	+

---

Смотрите также файлы

• Методы оптимизации Курсовой проект О распределении.docx

• Методы оптимизации Зыкина.docx

• РЕФЕРАТ_ФИЗКУЛЬТУРА.docx

• физра реферат.doc

• конкуренты.docx