Лекция
Привет, сегодня поговорим про алгоритм прима, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое алгоритм прима , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
алгоритм прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 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. Об этом говорит сайт https://intellect.icu . Алгоритм поддерживает следующий инвариант цикла, состоящий из трех частей.
Перед каждой итерацией цикла 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 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.
Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь 
реализована как обычный массив 
, то 
выполняется за 
, а стоимость операции 
составляет 
. Если представляет собой бинарную пирамиду, то стоимость снижается до 
, а стоимость возрастает до . При использовании фибоначчиевых пирамидоперация выполняется за , а за .
| Способ представления приоритетной очереди и графа | Асимптотика |
|---|---|
| Массив d, списки смежности (матрица смежности) |  |
| Бинарная пирамида, списки смежности |  |
| Фибоначчиева пирамида, списки смежности |  |
На этом все! Теперь вы знаете все про алгоритм прима, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое алгоритм прима и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про алгоритм прима
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов