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

Свойства и структура алгоритма

Общее описание алгоритма

Алгоритм Прима предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе.

Математическое описание алгоритма

Пусть задан связный неориентированный граф [math]\displaystyle{ G = (V, E) }[/math] с весами рёбер [math]\displaystyle{ f(e) }[/math]. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

Алгоритм Прима основан на следующих двух свойствах задачи:

• Минимальное ребро фрагмента. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева и [math]\displaystyle{ e_F }[/math] – ребро наименьшего веса, исходящее из [math]\displaystyle{ F }[/math] (т.е. ровно один его конец является вершиной из [math]\displaystyle{ F }[/math]). Если ребро [math]\displaystyle{ e_F }[/math] единственно, то оно принадлежит минимальному остовному дереву.
• Схлопывание фрагментов. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева графа [math]\displaystyle{ G }[/math], а граф [math]\displaystyle{ G' }[/math] получен из [math]\displaystyle{ G }[/math] склеиванием вершин, принадлежащих [math]\displaystyle{ F }[/math]. Тогда объединение [math]\displaystyle{ F }[/math] и минимального остовного дерева графа [math]\displaystyle{ G' }[/math] даёт минимальное остовное дерево исходного графа [math]\displaystyle{ G }[/math].

В начале работы алгоритма создаётся фрагмент, содержащий одну произвольную вершину графа. На каждом шаге выбирается ребро минимального веса, исходящее из текущего фрагмента. Это ребро помещается в минимальное остовное дерево, а его конец добавляется в текущий фрагмент. Процесс останавливается, когда у текущего фрагмента не остаётся исходящих рёбер. Тогда выбирается одна из ранее не посещённых вершин графа, и начиная с неё «выращивается» новый фрагмент. Алгоритм прекращает работу, когда посещены все вершины графа.

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

Основной объём вычислений в алгоритме Прима приходится на поддержание набора рёбер, выходящих из текущего фрагмента. Необходимо добавлять новые рёбра или вершины в набор, и находить ребро с наименьшим весом.

• При использовании списков вершин сложность [math]\displaystyle{ O(n^2) }[/math].
• При использовании бинарной кучи рёбер сложность [math]\displaystyle{ O(m \ln m) }[/math].
• При использовании бинарной кучи вершин и сортировке рёбер у каждой вершины сложность [math]\displaystyle{ O(m \ln n) }[/math].
• При использовании быстрой кучи сложность [math]\displaystyle{ O(m + n \ln^2 n) }[/math].
• При использовании фибоначчиевой кучи сложность [math]\displaystyle{ O(m + n \ln n) }[/math].