Центральный Дом Знаний - Алгоритм Прима

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

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

Вход:

  • Связный неориентированный граф G(V,E)

Выход:

  • Множество T рёбер минимального остовного дерева 

Обозначения:

  • d[i] — расстояние от i-й вершины до построенного дерева

  • p[i] — предок i-й вершины, то есть такая вершина u, что (i,u) легчайшее из всех рёбер соединяющее i с вершиной из построенного дерева.

  • w(i,j) — вес ребра (i,j)

  • Q — приоритетная очередь вершин графа, где ключ — d[i]

  • T — множество ребер минимального остовного дерева

Псевдокод:

 T \gets {}

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

d[i] \gets \infty

p[i] \gets nil

d[1] \gets 0

Q \gets V

v \gets\ Extract.min(Q)

Пока Q не пуста

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

Если u \in Q и w(v,u) < d[u]

d[u] \gets w(v,u)

p[u] \gets v

 v \gets Extract.Min(Q)

 T \gets T+(p[v],v) 

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


Способ представления графа и приоритетной очереди

Асимптотика

Массив d, списки смежности (матрица смежности)

O(V2)

Бинарная пирамида, списки смежности

O((V + E)log V) = O(Elog V)

Фибоначчиева пирамида, списки смежности

O(E + Vlog V)


Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24