Как построить минимальное остовное дерево: алгоритмы Прима и Краскала?

Минимальное остовное дерево (MST) — подмножество из `V − 1` рёбер связного неориентированного графа, соединяющее все вершины с минимальным суммарным весом. Прим и Краскал — жадные алгоритмы, корректные благодаря свойству разреза.

Свойство разреза

Для любого разбиения вершин на две части самое лёгкое ребро через разрез входит в какое-то MST. Если все веса различны, MST единственно.

Краскал

1. Отсортировать рёбра по весу.
2. Добавлять ребро, если его концы в разных компонентах (проверка через Union-Find).

• O(E log E) — доминирует сортировка. Удобен, когда граф задан списком рёбер и разрежен.
• На несвязном графе естественно даёт минимальный остовный лес.

Прим

1. Начать с любой вершины.
2. Повторять: взять самое лёгкое ребро из дерева в вершину вне дерева (куча).

• O(E log V) с бинарной кучей; O(V²) с простым массивом — лучше для плотных графов, где E ≈ V².
• Похож на Дейкстру, но ключ — вес одного ребра, а не расстояние от старта.

Нюансы

• Отрицательные веса допустимы — в отличие от Дейкстры.
• Применения: проектирование сетей (кабели, трубопроводы), кластеризация single-linkage (удалить k − 1 самых тяжёлых рёбер MST), 2-приближение метрического TSP.

Коротко для собеседования

MST соединяет все вершины самым дешёвым набором рёбер: Краскал сортирует рёбра и склеивает компоненты через Union-Find, Прим наращивает дерево от одной вершины с помощью кучи. Краскал удобен для разреженных графов в виде списка рёбер, Прим на массиве — для плотных; кратчайших путей MST не даёт.