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

Что такое остовное дерево

Остовное дерево связного графа — подграф, который содержит все вершины, связен и не имеет циклов. В нём ровно n − 1 ребро, где n — число вершин. Минимальное остовное дерево (МОД) — остовное дерево с наименьшей суммой весов рёбер. Классическая задача: проложить кабель, трубы или дороги между пунктами так, чтобы все были соединены, а суммарная длина или стоимость была минимальной.

Если граф несвязный, остовного дерева нет; вместо него строится остовный лес — по дереву на каждую компоненту связности, всего n − c рёбер, где c — число компонент.

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

Рёбра сортируются по возрастанию веса и просматриваются по очереди. Ребро добавляется в дерево, если соединяет вершины из разных частей, и отбрасывается, если образует цикл с уже выбранными рёбрами. Для быстрой проверки используется система непересекающихся множеств. Алгоритм останавливается, когда набрано n − c рёбер. Время работы — O(m log m), основное время уходит на сортировку.

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

Дерево выращивается из одной начальной вершины. На каждом шаге выбирается самое лёгкое ребро, которое соединяет вершину дерева с вершиной вне его, и эта вершина присоединяется к дереву. Время работы — O(n²) для плотных графов или O(m log n) с кучей. Если граф несвязный, после исчерпания компоненты калькулятор начинает новое дерево с первой непосещённой вершины.

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

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

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

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

Пример

В графе из примера 7 вершин и 11 рёбер. Крускал берёт рёбра по возрастанию веса: A–D (5), C–E (5), D–F (6), A–B (7), B–E (7). Ребро B–C (8) отбрасывается — B и C уже соединены через E; так же отбрасываются E–F (8) и B–D (9). Последним добавляется E–G (9). Получается 6 рёбер и суммарный вес 5 + 5 + 6 + 7 + 7 + 9 = 39.