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

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

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

В качестве входных данных алгоритму передаются связный граф G и корень r минимального остовного дерева. Все вершины G, еще не попавшие в дерево,хранятся в очереди с приоритетом Q. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле prev[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на вершину дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).

Формальное описание     [вверх]

MST_PRIM(G, w, r)
1    for (Для) каждой вершины u є V[G]
2            do key [u] «- INFINITY
3               prev[u] «- NIL
4    key[r] «- 0
5    Q «- V[G]
6    while Q не пустая
7            do u «- Extract_Min(Q)
8                  for (Для) каждой вершины v є Adj[u]
9                         do if v є Q и w(u,v) < key[v]
10                           then prev[v] «- u
11                                key[v] «- w(u, v)

В строках 1-5 ключи всех вершин устанавливаются равными INFINITY (за исключением корня r, ключ которого равен 0, так что он оказывается первой обрабатываемой вершиной), указателям на родителей для всех узлов присваиваются значения NIL и все вершины вносятся в очередь с приоритетами Q. Алгоритм поддерживает следующий инвариант цикла, состоящий из трех частей.

Перед каждой итерацией цикла while в строках 6-11

1. A={(v,prev[v]):v є V - {r} - Q};
2. вершины, уже помещенные в минимальное остовное дерево, принадлежат множеству V — Q;
3. для всех вершин v є Q справедливо следующее: если prev[v] != NIL, то key [v] < INFINITY и key [v] — вес легкого ребра (v,p[v]), соединяющего v с некоторой вершиной, уже находящейся в минимальном остовном дереве.

В строке 7 определяется вершина и, принадлежащая легкому ребру, пересекающему разрез (V — Q,Q) (за исключением первой итерации, когда и = r в соответствии с присвоением в строке 4). Удаление и из множества Q добавляет его в множество V — Q вершин дерева. Цикл for в строках 8-11 обновляет поля key и prev для каждой вершины v, смежной с u и не находящейся в дереве. Это обновление сохраняет третью часть инварианта.

Оценка сложности     [вверх]

Время работы алгоритма Прима зависит от выбранной реализации очереди с приоритетами Q. Если реализовать ее как бинарную пирамиду, то для выполнения инициализации в строках 1-5 потребуется времени О (V). Тело цикла while выполняется |V| раз, а поскольку каждая операция Extract_Min занимает время О (lg V), общее время всех вызовов процедур Extract__Min составляет О (V*lg V). Цикл for в строках 8-11 выполняется всего О (Е) раз, поскольку сумма длин всех списков смежности равна 2|Е|. Внутри цикла for проверка на принадлежность Q в строке 9 может быть реализована за постоянное время, если воспользоваться для каждой вершины битом, указывающим, находится ли она в Q, и обновлять этот бит при удалении вершины из Q. Присвоение в строке 11 неявно включает операцию Decrease_Key над пирамидой. Время выполнения этой операции — О (lg V). Таким образом, общее время работы алгоритма Прима составляет o(V * lg V + Е * lg V) = o(Е * lg V), что асимптотически совпадает со временем работы алгоритма Крускала.

Пример     [вверх ]

Выполнение алгоритма Прима:

1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер.

2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

3. Следующее безопасное ребро с весом 11. Добавляем его.

4-8. Добавляем остальные безопасные ребра.
                     

Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Визуализатор для алгоритма поиска построение минимального остовного дерева
(переключить в режим работы по алгоритму Прима)

Ещё один пример выполнения алгоритма Прима. Корневая вершина — а. Заштрихованные ребра принадлежат растущему дереву.

[вверх]