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

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

История

Идея алгоритма впервые была опубликована в 1930 году чешским математиком Войцехом Ярником в его работе «О минимальном остовном дереве». В 1957 году американский математик Роберт Прим, работая в Bell Labs, независимо разработал аналогичный алгоритм для решения задачи о соединении терминалов в телефонных сетях с минимальной стоимостью кабелей. Позднее, в 1959 году, Эдсгер Дейкстра также опубликовал описание этого алгоритма, что привело к тому, что в некоторых источниках он называется алгоритмом Прима-Дейкстры или алгоритмом Ярника-Прима-Дейкстры.

Описание алгоритма

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

Основные шаги

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

Псевдокод

`` function prim(G, start): T = пустое множество рёбер (остовное дерево) visited = пустое множество посещённых вершин добавить start в visited пока visited не содержит все вершины G: найти ребро (u, v) минимального веса, такое что u ∈ visited, v ∉ visited добавить v в visited добавить (u, v) в T вернуть T ``

Реализация

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

Простая реализация (для плотных графов)

Если граф задан матрицей смежности, а для хранения расстояний до ещё не включённых вершин используется массив, то временная сложность составляет O(V²), где V — количество вершин. Этот подход оптимален для плотных графов, где количество рёбер E близко к V².

Реализация с двоичной кучей

Для разреженных графов (E ≈ V) более эффективно использование очереди с приоритетами (двоичной кучи) для хранения минимальных рёбер, инцидентных текущему дереву. Временная сложность составляет O(E log V).

Реализация с фибоначчиевой кучей

Использование фибоначчиевой кучи позволяет достичь асимптотической сложности O(E + V log V), что является наилучшей теоретической оценкой для алгоритма Прима.

Пример работы

Рассмотрим граф с четырьмя вершинами: A, B, C, D и рёбрами: AB (вес 1), AC (вес 3), AD (вес 4), BC (вес 2), CD (вес 5).

1. Начало: Выбираем вершину A. Дерево = {A}.
2. Шаг 1: Минимальное ребро, соединяющее A с другими вершинами — AB (вес 1). Добавляем B. Дерево = {A, B}, рёбра = {AB}.
3. Шаг 2: Из вершин A и B минимальные рёбра к C: AC (3) и BC (2). Выбираем BC (2). Добавляем C. Дерево = {A, B, C}, рёбра = {AB, BC}.
4. Шаг 3: Осталась вершина D. Рёбра к ней: AD (4) и CD (5). Выбираем AD (4). Добавляем D. Дерево = {A, B, C, D}, рёбра = {AB, BC, AD}.

Итоговое минимальное остовное дерево имеет суммарный вес 1 + 2 + 4 = 7.

Свойства и корректность

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

Сравнение с другими алгоритмами

Алгоритм Прима является одним из трёх классических алгоритмов для построения минимального остовного дерева, наряду с алгоритмом Краскала и алгоритмом Борувки.

Алгоритм Прима vs Алгоритм Краскала

• Принцип работы: Алгоритм Прима строит дерево, постепенно наращивая его от одной вершины. Алгоритм Краскала изначально рассматривает каждую вершину как отдельное дерево и последовательно объединяет их, добавляя рёбра минимального веса, не образующие циклов.
• Структуры данных: Алгоритм Прима эффективно использует очереди с приоритетами. Алгоритм Краскала — структуру данных «система непересекающихся множеств» (DSU).
• Применимость: Алгоритм Прима, как правило, эффективнее на плотных графах (с большим количеством рёбер), в то время как алгоритм Краскала показывает лучшие результаты на разреженных графах.

Алгоритм Прима vs Алгоритм Борувки

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

Применение

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

• Проектирование сетей: Прокладка кабелей (телефонных, электрических, интернет-кабелей) между городами или зданиями с минимальной стоимостью.
• Кластеризация данных: В задачах машинного обучения и анализа данных для построения иерархических кластеров (например, алгоритм MST-кластеризации).
• Компьютерное зрение: Для сегментации изображений, где пиксели рассматриваются как вершины графа, а веса рёбер отражают разницу в цвете или яркости.
• Транспортные сети: Построение дорожных сетей, трубопроводов или линий электропередач, соединяющих населённые пункты.
• Приближённые алгоритмы: Используется как составная часть в приближённых алгоритмах для решения задачи коммивояжёра (например, алгоритм Кристофидеса).

Интересные факты

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

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2001.
• Прим Р. К. Кратчайшие связывающие сети и некоторые обобщения // Bell System Technical Journal. — 1957. — Т. 36, № 6. — С. 1389–1401.
• Ярник В. О минимальном остовном дереве // Práce Moravské Přírodovědecké Společnosti. — 1930. — Т. 6. — С. 57–63.