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

Описание На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.

Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

Пример Изображение Множество выбранных вершин U Ребро (u, v) Множество невыбранных вершин V \ U Описание {} {A,B,C,D,E,F,G}Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами. {D} (D,A) = 5 V (D,B) = 9(D,E) = 15(D,F) = 6 {A,B,C,E,F,G}В качестве начальной произвольно выбирается вершина D. Каждая из вершин A, B, E и F соединена с D единственным ребром. Вершина A — ближайшая к D, и выбирается как вторая вершина вместе с ребром AD. {A,D} (D,B) = 9(D,E) = 15(D,F) = 6 V(A,B) = 7 {B,C,E,F,G}Следующая вершина — ближайшая к любой из выбранных вершин D или A. B удалена от D на 9 и от A — на 7. Расстояние до E равно 15, а до F — 6. F является ближайшей вершиной, поэтому она включается в дерево F вместе с ребром DF. {A,D,F} (D,B) = 9(D,E) = 15(A,B) = 7 V(F,E) = 8(F,G) = 11 {B,C,E,G}Аналогичным образом выбирается вершина B, удаленная от A на 7. {A,B,D,F} (B,C) = 8(B,E) = 7 V(D,B) = 9 цикл(D,E) = 15(F,E) = 8(F,G) = 11 {C,E,G}В этом случае есть возможность выбрать либо C, либо E, либо G. C удалена от B на 8, E удалена от B на 7, а G удалена от F на 11. E — ближайшая вершина, поэтому выбирается E и ребро BE. {A,B,D,E,F} (B,C) = 8(D,B) = 9 цикл(D,E) = 15 цикл(E,C) = 5 V(E,G) = 9(F,E) = 8 цикл(F,G) = 11 {C,G}Здесь доступны только вершины C и G. Расстояние от E до C равно 5, а до G — 9. Выбирается вершина C и ребро EC. {A,B,C,D,E,F} (B,C) = 8 цикл(D,B) = 9 цикл(D,E) = 15 цикл(E,G) = 9 V(F,E) = 8 цикл(F,G) = 11 {G}Единственная оставшаяся вершина — G. Расстояние от F до неё равно 11, от E — 9. E ближе, поэтому выбирается вершина G и ребро EG. {A,B,C,D,E,F,G} (B,C) = 8 цикл(D,B) = 9 цикл(D,E) = 15 цикл(F,E) = 8 цикл(F,G) = 11 цикл {}Выбраны все вершины, минимальное остовное дерево построено (выделено зелёным). В этом случае его вес равен 39.

Реализация

Обозначения  — расстояние от -й вершины до построенного дерева  — предок -й вершины, то есть такая вершина , что легчайшее из всех рёбер, соединяющее i с вершиной из построенного дерева.  — вес ребра  — приоритетная очередь вершин графа, где ключ —  — множество ребер минимального остовного дерева

Псевдокод

Для каждой вершины

Пока не пуста Для каждой вершины смежной с Если и

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

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

См. также Минимальное остовное дерево Остовное дерево Алгоритм Борувки Алгоритм Дейкстры Алгоритм обратного удаления Алгоритм Краскала

Литература V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. R. C. Prim: Shortest connection networks and some generalizations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401 D. Cheriton and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal on Computing, 5 (Dec. 1976), pp. 724–741 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 0-262-03384-4. Section 23.2: The algorithms of Kruskal and Prim, pp. 631–638.

Ссылки Описание и реализация Алгоритма Прима

Прима Прима Категория:Остовное дерево