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

  • Текущая
  • В дереве
  • Рядом с деревом
  • Лучшее ребро пока
  • Замкнуло бы цикл

Подробнее о минимальных остовных деревьях

Минимальное остовное дерево

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

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

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

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

Отсортируйте все ребра от самого короткого к самому длинному и проверяйте их в этом порядке. Если ребро соединяет две части, которые еще не связаны, оно входит в дерево. Если его концы уже связаны через дерево, оно замкнуло бы цикл, поэтому его пропускают. Остановитесь, когда в дереве на одно ребро меньше, чем вершин. Чтобы быстро узнать, связаны ли уже две вершины, алгоритм Краскала хранит части в системе непересекающихся множеств (union-find).

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

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

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

Что такое минимальное остовное дерево?

Для связного графа, у ребер которого есть длины, остовное дерево — это набор ребер, который соединяет все вершины без единого цикла; при n вершинах в нем всегда n − 1 ребер. Минимальное остовное дерево — это остовное дерево с наименьшей возможной общей длиной.

Чем алгоритм Краскала отличается от алгоритма Прима?

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

Единственно ли минимальное остовное дерево?

Да, если все длины ребер разные. Если некоторые длины равны, может быть несколько деревьев с одинаковой наименьшей суммой, и алгоритмы могут выбрать разные, в зависимости от того, как они выбирают между равными ребрами.

Минимальное остовное дерево — это то же самое, что кратчайшие пути?

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

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

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

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

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

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