Алгоритмы

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

Цели урока

Понять задачу MST
Реализовать Kruskal с Union-Find
Реализовать Prim с priority queue
Знать когда какой алгоритм лучше

Предварительные знания

Графы
Union-Find

Задача: спроектировать электросеть для деревни. Нужно соединить все дома минимальной длиной проводов. Это классическая задача MST, которую решили ещё в 1926 году!

Проектирование сетей (электрических, телекоммуникационных)
Кластеризация данных
Приближённый алгоритм для TSP
Сегментация изображений

Электросеть Борувки и алгоритмы, выросшие из неё

Задача о минимальном остовном дереве началась с реального инженерного вопроса. В 1926 году чешского математика Отакара Борувку попросили спроектировать электросеть для Моравии с минимальной общей длиной проводов, и он опубликовал первый алгоритм MST, чтобы решить её, за годы до того, как теория графов оформилась в отдельную дисциплину. Его метод объединяет компоненты параллельными раундами, поэтому он снова в моде для параллельных и распределённых вычислений. В 1930 году его соотечественник Войтех Ярник описал подход с выращиванием из одной вершины. Тот же алгоритм заново открыли Роберт Прим в 1957 году и Дейкстра в 1959, так что 'алгоритм Прима' правильнее называть алгоритмом Ярника-Прима. Джозеф Краскал опубликовал свой подход с сортировкой рёбер в 1956 году в статье на четыре страницы. Три классических алгоритма, три разные стратегии, все решают одну и ту же задачу и все обоснованы одним свойством разреза: самое лёгкое ребро, пересекающее любой разрез, можно безопасно добавить в MST.

Идея: соединить все минимальным весом

**Задача:** соединить все вершины так, чтобы сумма весов рёбер была минимальной.

**Свойства MST:**

Содержит ровно V-1 рёбер (это дерево)
Связывает все V вершин
Имеет минимальную сумму весов
Может быть не единственным (при равных весах)

**Жадный выбор работает!** На каждом шаге берём «лучшее» ребро - и получаем глобальный оптимум. Это редкость!

MST для графа с V вершинами содержит:

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

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

**Идея Краскала:** сортируем рёбра по весу и жадно берём, если не образует цикл.

Операция	Сложность
Сортировка рёбер	O(E log E)
E операций Union-Find	O(E α(V)) ≈ O(E)
Итого	O(E log E) = O(E log V)

Зачем Kruskal использует Union-Find?

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

Представь краску, которая растекается по карте от одного города. На каждом шаге «пятно» расширяется к ближайшему ещё не закрашенному городу. Соединяющее ребро становится частью дерева. **Алгоритм Прима** работает именно так - дерево растёт как живой организм, всегда захватывая самого ближнего соседа.

**Идея Прима:** растим дерево из одной вершины, добавляя ближайшее ребро к «облаку».

Реализация Prim	Сложность
Наивная (массив)	O(V²)
Binary Heap	O((V + E) log V)
Fibonacci Heap	O(E + V log V)

Prim похож на Dijkstra. В чём отличие?

Kruskal vs Prim

	Kruskal	Prim
Подход	Глобальный (все рёбра)	Локальный (растим дерево)
Структура данных	Union-Find	Priority Queue
Разреженный граф	Лучше: O(E log E)	Хуже: O(E log V)
Плотный граф	Хуже: O(V² log V)	Лучше: O(V²) наивный
Параллелизация	Сложно	Проще

**Применения MST:**

**Проектирование сетей:** минимальная длина кабеля
**Кластеризация:** удаляем k-1 самых тяжёлых рёбер MST → k кластеров
**Приближённые алгоритмы:** TSP приближение через MST
**Компьютерное зрение:** сегментация изображений

Для графа дорожной сети (V=10000, E=30000) лучше использовать: