Алгоритм Прима
Представьте, что вы прокладываете кабель от электростанции: сначала подключаете ближайший город, затем город, ближайший к чему-то уже подключенному, и так далее. Это и есть алгоритм Прима, и он всегда приводит к самой дешевой возможной сети.
Идея
Минимальное остовное дерево соединяет все вершины взвешенного графа с наименьшей возможной общей длиной ребер. Алгоритм Прима строит его, наращивая одно дерево наружу от старта. Дерево никогда не распадается на части: на каждом шаге к нему присоединяется ровно одна новая вершина, по самому короткому ребру, ведущему из дерева.
По шагам
Поместите старт в дерево. Для каждой вершины вне дерева храните ее лучшее ребро: самое короткое ребро к какой-либо вершине дерева. Затем повторяйте: выберите вершину вне дерева с самым коротким лучшим ребром, добавьте ее в дерево вместе с этим ребром и проверьте ее ребра. Сосед вне дерева, до которого теперь можно дойти по более короткому ребру, получает это ребро как новое лучшее. Остановитесь, когда все вершины будут в дереве.
Пример
Возьмите ребра A–B длиной 1, B–C 2, A–C 3, C–D 4 и B–D 5 и начните с A. Ребра из A дают B лучшее ребро 1, а C — лучшее ребро 3. B ближе всех, поэтому присоединяется по A–B; ребра из B улучшают C до 2 и дают D 5. C присоединяется по B–C, а ребро C–D улучшает D до 4. Наконец, D присоединяется по C–D. Общая длина дерева A–B, B–C, C–D равна 1 + 2 + 4 = 7.
Почему это верно
На каждом шаге вершины разделены на две группы: в дереве и вне его. Свойство разреза говорит, что самое короткое ребро между двумя такими группами всегда входит в какое-нибудь минимальное остовное дерево. Прим всегда добавляет именно это ребро, поэтому построенное к этому моменту дерево всегда можно достроить до минимального остовного, а когда присоединятся все вершины, оно само им станет.
История и скорость
Чешский математик Войтех Ярник опубликовал алгоритм в 1930 году. Роберт Прим заново открыл его в Bell Labs в 1957 году, а Эдсгер Дейкстра — еще раз в 1959 году. Если ожидающие вершины хранятся в двоичной куче, работа растет как E log V для V вершин и E ребер; с обычным массивом — около V², что лучше, когда соединена почти каждая пара вершин. С фибоначчиевой кучей — E + V log V.
Попробуйте сами
Откройте приложение, щелкните вершину, чтобы начать с нее, и нажмите Шаг. Вершины в дереве зеленые, ожидающие — синие, а лучшее ребро каждой ожидающей вершины нарисовано пунктиром. Ожидающие вершины перечислены под графом с длиной их лучшего ребра, от самой короткой: первая присоединится следующей. Начинайте с разных вершин и смотрите, как меняется порядок, а общая длина остается прежней.
Часто задаваемые вопросы
Чем алгоритм Прима отличается от алгоритма Дейкстры?
Оба наращивают область от старта с помощью очереди с приоритетом. Прим упорядочивает ожидающую вершину по длине ее единственного лучшего ребра к дереву, Дейкстра — по всему расстоянию от старта. Прим дает минимальное остовное дерево, Дейкстра — дерево кратчайших путей.
Работает ли алгоритм Прима с отрицательными длинами ребер?
Да. В отличие от алгоритма Дейкстры, Прим только сравнивает ребра между собой, поэтому отрицательные длины не мешают: он все равно находит остовное дерево с наименьшей суммой.
Что, если граф несвязный?
Тогда алгоритм Прима останавливается, когда дойдет до всех вершин, до которых может: он дает минимальное остовное дерево только той части графа, где находится старт. Если снова запустить его с еще не достигнутой вершины, получится минимальный остовный лес.
Что лучше: алгоритм Прима или алгоритм Краскала?
Ни один не выигрывает всегда. Прим подходит для плотных графов и графов, хранящихся в виде списков соседей; Краскал — для разреженных графов, заданных списком ребер. Оба находят дерево одной и той же общей длины.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать алгоритм Прима