Минимальное остовное дерево (MST) связного неориентированного взвешенного графа — остовное дерево с минимальной суммой весов рёбер. Классический жадный алгоритм Краскала просматривает рёбра в порядке неубывания веса и добавляет очередное ребро, только если оно не создаёт
Корректность основана на свойстве разреза: минимальное по весу допустимое ребро, пересекающее разрез между компонентами текущего леса, можно включить в некоторое MST. При сортировке рёбер алгоритм работает за \(O(|E|\log|E|)\). Проверку компонент удобно выполнять структурой непересекающихся множеств.
Что важно запомнить
- MST соединяет все вершины, не содержит циклов и имеет \(|V|-1\) ребро.
- Краскал рассматривает рёбра по неубыванию веса.
- Ребро добавляется, если его концы лежат в разных компонентах текущего леса.
- Свойство разреза обосновывает безопасность каждого жадного
- Основная стоимость реализации — сортировка рёбер. Union-Find ускоряет проверки связности компонент.
Алгоритм Краскала
Начинают с леса из изолированных вершин и пустого множества рёбер \(T\). Все рёбра сортируют по неубыванию веса. Затем последовательно рассматривают ребро \(e=\{u,v\}\). Если \(u\) и \(v\) находятся в разных компонентах текущего леса, ребро добавляют в \(T\). Если они уже находятся в одной компоненте, ребро пропускают, потому что оно создало бы цикл. Работа заканчивается после выбора \(|V|-1\)
Почему жадный выбор корректен
Перед добавлением ребра \(e\) его концы находятся в разных компонентах. Возьмём разрез, одной стороной которого является компонента, содержащая \(u\). Ребро \(e\) пересекает этот разрез. Поскольку рёбра просматриваются в порядке веса, среди ещё допустимых пересекающих рёбер нет более лёгкого.
Если некоторый минимальный остов \(T^*\) не содержит \(e\), добавление \(e\) к \(T^*\) создаёт цикл. В этом цикле есть другое ребро \(f\), пересекающее тот же разрез. Вес \(e\) не больше веса \(f\). Заменив \(f\) на \(e\), получаем остовное дерево не большего веса. Значит существует MST, содержащий сделанный жадный выбор. Повторяя аргумент, получаем корректность всего
Сложность
Сортировка занимает \(O(|E|\log|E|)\). Операции поиска компонент и их объединения с Union-Find дают почти линейную добавку, поэтому общая стандартная оценка остаётся \(O(|E|\log|E|)\).
Пример простыми словами
В треугольнике с весами рёбер 1, 2 и 3 Краскал сначала берёт рёбра весов 1 и 2. После этого все три вершины уже связаны. Ребро веса 3 образовало бы цикл и пропускается. Вес MST равен 3.
Частые ошибки
- Путать минимальное остовное дерево с деревом кратчайших путей от одной вершины. MST минимизирует суммарный вес всего остова, а не расстояния от корня.
- Добавлять очередное самое лёгкое ребро без проверки цикла.
- Считать, что при равных весах алгоритм некорректен. MST может быть не единственным, но Краскал всё равно строит один из минимальных остовов.
