Минимальное остовное дерево Краскала
Добавляйте самые дешёвые рёбра без циклов
«Минимальное остовное дерево Краскала» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Что такое MST
Минимальное остовное дерево соединяет каждую вершину, используя минимальную суммарную стоимость рёбер и не образуя циклов. Представьте, что Вы прокладываете провода в городе с наименьшими затратами. 🌲
Основная идея Крускала
Алгоритм Крускала основан на жадном подходе: добавляйте самое дешёвое ребро, которое не образует цикл, пока весь граф не окажется соединён.
Шаг первый: sort рёбер
Сначала выполните sort всех рёбер по весу, начиная с наименьшего. Жадный выбор дешёвых рёбер обеспечивает минимальную итоговую стоимость.
edges.sort() # (weight, u, v)Почему DSU подходит идеально
Добавление ребра образует цикл только тогда, когда его концы уже соединены. DSU проверяет связность почти за константное время. 🤝
Обход отсортированных рёбер
Рассматривайте рёбра от самых дешёвых к самым дорогим. Для каждого проверьте, имеют ли его концы один и тот же корень в DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Принять или отклонить
Если корни различаются, ребро соединяет две отдельные части, поэтому примите его и объедините эти части. Если корни совпадают, пропустите ребро, чтобы избежать цикла.
if ru != rv:
union(u, v)
total += wЗнайте, когда остановиться
Остовное дерево на n вершинах содержит ровно n минус 1 ребро. Получив это количество рёбер, можно досрочно остановиться.
Обнаружение несвязности
Если после рассмотрения всех рёбер принято меньше чем n минус 1 ребро, граф несвязен, и остовного дерева не существует.
Затраты времени
Основное время занимает сортировка, поэтому алгоритм Крускала работает за O(E log E). Операции DSU настолько дёшевы, что почти не увеличивают эту общую оценку.
Почему жадный подход корректен
Свойство разреза гарантирует, что самое лёгкое ребро, пересекающее любое разбиение, безопасно добавлять. Именно поэтому выбор рёбер от самых дешёвых к самым дорогим никогда не приводит к ошибке.
Когда выбирать Крускала
Алгоритм Крускала особенно хорош для разреженных графов, заданных списком рёбер, — именно такой формат чаще всего непосредственно предоставляют в задачах соревнований. ⚡
Быстрая проверка
Определите, по какому признаку алгоритм Крускала отклоняет ребро.
Повторение
Вы построили MST Крускала: выполнили sort рёбер, добавляли самые дешёвые рёбра, соединяющие две компоненты через DSU, и остановились после получения n минус 1 ребра. 🎉
Часто задаваемые вопросы
Урок «Минимальное остовное дерево Краскала» бесплатный?
Да — полный текст урока «Минимальное остовное дерево Краскала» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Минимальное остовное дерево Краскала»?
Добавляйте самые дешёвые рёбра без циклов Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Минимальное остовное дерево Краскала»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- DSU со сжатием путей
- Объединение по рангу и компоненты
- Минимальное остовное дерево Краскала
- MST Прима с кучей