Информатика / Алгоритмы и анализ данных

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

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.

Опубликовано: 20 октября 2026 г.Обновлено: 20 октября 2026 г.

Формула

T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1

Схема Краскал: принятые рёбра

AB + BC + CD = 1 + 2 + 4 = 7

Обозначения

$T,S$: остовные деревья, содержащие все вершины, множество рёбер
$w(e)$: стоимость отдельного ребра, единица стоимости
$V$: число вершин исходного графа, количество
$|T|$: число рёбер выбранного дерева, количество

Условия применения

Граф неориентированный; для единого остовного дерева он должен быть связным. Стоимости рёбер складываются в одной единице и не зависят от набора других рёбер. Равные и отрицательные веса допустимы, но равенства могут давать несколько минимальных деревьев.

Ограничения

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

Подробное объяснение

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

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

В связной сети процесс заканчивается после V−1 принятых рёбер. Это число характеризует любое дерево с V вершинами, но само по себе не доказывает оптимальности: важны порядок весов и отказ от циклов. Минимальная сумма получается именно благодаря безопасному выбору соединений.

Для быстрого ответа «в одной ли компоненте концы» применяют систему непересекающихся множеств. Сортировка обычно определяет основное время O(E log E). При одинаковых весах порядок может изменить состав дерева, но его минимальный суммарный вес сохранится.

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

Как пользоваться формулой

Проверьте связность и неориентированность модели, затем отсортируйте все рёбра по возрастанию их стоимости.
Начните с отдельных компонент; у каждого очередного ребра определите, принадлежат ли его концы разным компонентам.
При разных компонентах примите ребро и объедините их; при одинаковой пропустите ребро, чтобы не создавать цикл.
Для связного графа остановитесь после V−1 принятых рёбер, просуммируйте их веса и отдельно проверьте связность результата.

Историческая справка

Джозеф Краскал опубликовал On the shortest spanning subtree of a graph and the traveling salesman problem в Proceedings of the American Mathematical Society в 1956 году. В названии упомянуты две задачи, но минимальное остовное дерево не является готовым решением задачи коммивояжёра: дерево допускает вершины разных степеней и не обязано образовывать цикл. Современное изложение отделяет жадный выбор рёбер от структуры данных, которая отслеживает компоненты. В учебных материалах Princeton алгоритм рассматривается через свойство разреза и систему непересекающихся множеств. Такая форма делает доказательство оптимальности независимым от конкретного языка программирования. Здесь используется общепринятое имя метода без утверждения, что вся теория минимальных деревьев возникла из одной публикации.

Историческая линия формулы

Название дано по Джозефу Краскалу и статье 1956 года. Историческая связь относится к алгоритму выбора рёбер для минимального остова. Современная реализация через объединение компонент и общая теория сетевой оптимизации не приписываются одной программной версии.

Пример

В неориентированном графе четыре вершины A,B,C,D. Рёбра: AB = 1, BC = 2, AC = 3, CD = 4, BD = 5. Берём AB, затем BC: уже соединены A,B,C, сумма 3. Ребро AC весом 3 пропускаем, поскольку его концы находятся в одной компоненте и возник бы цикл A–B–C–A. Принимаем CD весом 4 и получаем три ребра AB,BC,CD общей стоимости 1+2+4 = 7. Все четыре вершины соединены, а число рёбер равно V−1 = 3. Проверка минимальности: D можно присоединить не дешевле чем за 4, а связать A,B,C — не дешевле чем рёбрами 1 и 2. Нижняя граница 4+1+2 = 7 достигнута. Все стоимости заданы в одинаковых условных единицах.

Частая ошибка

Не берите просто V−1 самых дешёвых рёбер без проверки циклов. Не применяйте правило к ориентированному графу как к той же задаче. Не путайте минимальный остов с кратчайшими путями от старта. Не объявляйте лес связным деревом. Не запрещайте отрицательные веса: для остова они допустимы.

Практика

Задачи с решением

Равные веса

Условие. В треугольнике AB = AC = BC = 2. Найдите минимальный вес остова и число подходящих деревьев.

Решение. Нужно два ребра; любые два соединяют все вершины без цикла. Каждая сумма равна 2+2 = 4. Из трёх рёбер можно исключить любое одно.

Ответ. Вес 4; три минимальных дерева.

Несвязная сеть

Условие. Граф содержит только рёбра AB = 1 и CD = 2. Что построит Краскал?

Решение. Оба ребра принимаются, но связать компоненты {A,B} и {C,D} нечем. Общая сумма 3 относится к лесу из двух деревьев, не к остову всего графа.

Ответ. Минимальный лес веса 3; единого остова нет.

Дополнительные источники

https://www.cs.yale.edu/homes/lans/readings/routing/kruskal-1956.pdf
https://algs4.cs.princeton.edu/43mst/index.php
https://algs4.cs.princeton.edu/lectures/keynote/43MinimumSpanningTrees.pdf

Связанные формулы

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

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

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

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

Информатика

Алгоритм Беллмана — Форда: путь с отрицательными весами

$d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)$

Алгоритм Беллмана — Форда уточняет расстояния последовательными проходами по рёбрам. Он допускает отрицательные веса и позволяет обнаружить отрицательный цикл, достижимый из выбранного источника.

Информатика

Алгоритм Флойда — Уоршелла: пути между всеми парами

$d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)$

Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.