Ребра дерева
Общая длина
Проверенные ребра

  • Текущая
  • В дереве
  • Рядом с деревом
  • Лучшее ребро пока

Подробнее об алгоритме Прима

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

Алгоритм Прима строит минимальное остовное дерево — самый дешевый набор ребер, соединяющий все вершины, — наращивая одно дерево от старта. На каждом шаге он добавляет вершину, до которой из дерева можно дойти по самому короткому ребру. Щелкните вершину, чтобы начать с нее, и пройдите по шагам: вы увидите ожидающие вершины, их лучшие ребра и то, как растет дерево. Нажмите Пуск, чтобы посмотреть, как растет дерево, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом: дерево растет от нее. Число на каждом ребре — его длина. Под графом — вершины, ожидающие присоединения, у каждой указана длина ее лучшего ребра к дереву; само ребро нарисовано пунктиром. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом: дерево растет от нее.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
  3. Следите за ожидающими вершинами под графом, у каждой указано ее лучшее ребро к дереву. Кнопка Новый граф создает другой граф для пробы.

Как работает алгоритм Прима

Начните с дерева из одной вершины. Каждая вершина вне дерева помнит свое самое короткое ребро к дереву, если оно есть. Раз за разом берите вершину с самым коротким ребром, добавляйте ее вместе с этим ребром в дерево и проверяйте ее ребра: если какое-то из них короче, чем лучшее на данный момент ребро соседа, оно становится лучшим ребром этого соседа. Когда присоединятся все вершины, в дереве будет на одно ребро меньше, чем вершин, а его общая длина будет наименьшей из возможных.

Прим и Дейкстра

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

Часто задаваемые вопросы

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

Жадный алгоритм, который строит минимальное остовное дерево взвешенного графа, наращивая одно дерево от стартовой вершины и всегда добавляя самое короткое ребро, соединяющее дерево с вершиной вне его.

Важна ли стартовая вершина?

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

Кто придумал алгоритм Прима?

Первым его описал Войтех Ярник в 1930 году. Роберт Прим открыл его заново в 1957 году, а Эдсгер Дейкстра — в 1959 году, поэтому его называют также алгоритмом Ярника или алгоритмом Прима — Ярника.

Насколько быстр алгоритм Прима?

С двоичной кучей работа растет как E log V для V вершин и E ребер. С простым массивом вместо кучи нужно около V² шагов, что лучше для плотных графов, где соединена почти каждая пара вершин.

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и дерево строится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор