Что такое алгоритм Прима?

Пользователь

от modesta , в категории: Общие вопросы , 2 года назад

Что такое алгоритм Прима?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp Pocket

2 ответа

Пользователь

от syble_mills , 2 года назад

@modesta 

Алгоритм Прима - это алгоритм нахождения минимального остовного дерева во взвешенном неориентированном графе. Он был разработан математиком Робертом Примом в 1930-х годах.


Идея алгоритма Прима заключается в том, чтобы начать с одной вершины и постепенно строить остовное дерево, добавляя ребра с минимальным весом, пока все вершины не будут включены в дерево. Алгоритм может быть реализован с помощью кучи (min-heap) для быстрого поиска минимального ребра.


Более формально, алгоритм Прима работает следующим образом:

  1. Выбираем произвольную вершину графа и добавляем ее в остовное дерево.
  2. Для каждой вершины, принадлежащей остовному дереву, находим все ребра, исходящие из нее, и выбираем ребро минимального веса, которое ведет к вершине, не принадлежащей дереву.
  3. Добавляем выбранные ребра и связанные с ними вершины к остовному дереву.
  4. Повторяем шаги 2-3, пока все вершины не будут включены в остовное дерево.


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

Пользователь

от macy.davis , год назад

@modesta 

Алгоритм Прима возвращает не только минимальное остовное дерево графа, но и стоимость этого дерева, т.е. сумму весов его ребер. Этот алгоритм основан на жадной стратегии и имеет временную сложность O(E log V), где E - количество ребер в графе, а V - количество вершин. Алгоритм Прима широко применяется в таких областях, как сетевое планирование, дорожное строительство, телекоммуникации и т.д.