Информатика / Алгоритмы и анализ данных

Алгоритм Прима: минимальное остовное дерево

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

Опубликовано: 26 октября 2026 г.Обновлено: 26 октября 2026 г.

Формула

e_k\in\operatorname*{arg\,min}_{u\in S_k,\ v\notin S_k}w(u,v),\quad S_{k+1}=S_k\cup\{v\},\quad W(T)=\sum_{e\in T}w(e)

Схема Прим: выделенный остов имеет вес 8

Зелёные рёбра AB,BC,CD,DE образуют дерево; серые остаются вне остова. Граф неориентирован.

Обозначения

$Sₖ$: вершины уже построенной части дерева, множество
$w(u,v)$: вес ребра между вершинами, единая единица стоимости
$eₖ$: минимальное ребро текущего разреза, ребро
$W(T)$: суммарный вес остова, единица стоимости

Условия применения

Граф конечен, неориентирован и связен; веса рёбер сравнимы и имеют единый смысл. Отрицательные веса допустимы. При равных весах выбирают любое минимальное допустимое ребро, поэтому сам остов может быть неединственным при одной минимальной сумме.

Ограничения

В несвязном графе запуск из одной вершины покрывает только компоненту; для леса нужно повторение по компонентам. Метод не решает задачу кратчайших путей и не применяется напрямую к ориентированному остову. Ограничения на степень вершин или резервирование рёбер меняют задачу.

Подробное объяснение

Начните с одной вершины. На каждом шаге рассматриваются только рёбра между собранной частью S и внешними вершинами. Минимальное из них добавляет ровно одну новую вершину, поэтому цикл не возникает. После V−1 добавлений получено связное дерево.

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

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

Дейкстра внешне похожа выбором минимального ключа, но ключ имеет другой смысл. У Прима это вес одного ребра к дереву; у Дейкстры — накопленная длина пути от источника. Минимальная сумма всех рёбер остова не гарантирует кратчайший маршрут между каждой парой вершин.

Как пользоваться формулой

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

Историческая справка

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

В учебных изложениях XX–XXI веков центральным стал выбор структуры данных для внешних вершин. Лекция MIT об остовах показывает один алгоритм с массивом, двоичной и фибоначчиевой кучами; время работы меняется вместе со стоимостью операций очереди. В Algorithms Седжвика и Уэйна минимальный остов отделён от кратчайших путей. Современная формула выбора ребра выражает эту жадную границу, а не общий рецепт поиска минимального маршрута.

Историческая линия формулы

Метод традиционно называют алгоритмом Прима. Здесь используется стандартная схема роста одного дерева через минимальное ребро разреза, изложенная в MIT и Algorithms. Реализация через конкретную очередь меняет сложность, но не математическое правило выбора.

Пример

Пусть рёбра неориентированного графа: AB=2, AC=5, BC=1, BD=4, CD=3, CE=6, DE=2. Стартуем из A. Через первую границу дешевле AB=2. Для S={A,B} минимально BC=1. Теперь S={A,B,C}, наружу идут BD=4, CD=3, CE=6, поэтому берём CD=3. Последнюю вершину E присоединяет DE=2, а не CE=6. Итог: четыре ребра на пяти вершинах, вес 2+1+3+2=8. Проверка по Краскалу на том же графе также даёт рёбра BC, AB, DE, CD с суммой 8. Все вершины связаны, циклов нет; веса считаются в условных единицах стоимости, а не как длины путей от A.

Частая ошибка

Минимум ищут только через границу S, а не среди всех ещё не взятых рёбер. Ключ Прима нельзя заменить накопленным расстоянием от старта. Отрицательные веса не нарушают алгоритм. Равные веса не обязательно означают единственность дерева, а несвязность нельзя скрывать неполным результатом.

Практика

Задачи с решением

Треугольник

Условие. AB=5, AC=2, BC=1. Постройте остов Прима из A.

Решение. Сначала AC=2, затем из {A,C} берём CB=1 вместо AB=5. Сумма 3.

Ответ. AC и CB, вес 3.

Отрицательное ребро

Условие. AB=−2, BC=1, AC=4. Каков минимальный вес остова?

Решение. AB и BC соединяют три вершины без цикла; сумма −2+1=−1. Остальные деревья имеют веса 2 и 5.

Ответ. −1.

Дополнительные источники

https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/bb54568c86c60d86b25e9c1111470384_MIT6_046JS12_lec04.pdf
https://algs4.cs.princeton.edu/43mst/

Связанные формулы

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

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