Почему алгоритм Краскала встречается почти каждый год
Минимальное остовное дерево — частый мотив заданий №27 и №28. Школьник должен найти дешёвое соединение всех вершин. Экзаменаторы любят именно Краскала. Он интуитивен и легко проверяется руками. Если знать идею, решение занимает пару строчек кода или пять-шесть строк в бланке. Поэтому разбор алгоритма входит в любой быстрый план подготовки. Три месяца — реальный срок, но без чёткой карты не обойтись.
Графы и формулировки в условиях экзамена
В ЕГЭ используют ненагруженные термины. Рёбра называют дорогами, проводами или трубами. Стоимости даются целыми числами. Граф обычно неориентирован. Число вершин — от 5 до 20. Иногда присутствуют параллельные рёбра, но петель нет. Требуется либо сумма длин минимального дерева, либо сами рёбра в порядке добавления. Редко, но бывает вопрос про альтернативные стоимости при изменении одного веса. Пример формулировки:
- «Определите суммарную длину самого дешёвого соединения деревень».
- «Запишите номера дорог, входящих в минимальное остовное дерево».
Если встречается слово «самое дешёвое соединение всех городов», сразу вспоминаем Краскала либо Прима. Краскал проще выполнять вручную: сортировка, добавление, проверка циклов.
Пошаговая логика алгоритма Краскала
Алгоритм строит остовное дерево по возрастающей стоимости рёбер.
- Сортируем рёбра в порядке возрастания веса.
- Берём очередное ребро.
- Если его концы лежат в разных компонентах, соединяем их.
- Повторяем, пока не добавлено n-1 ребро, где n — число вершин.
Проверка «в разных ли компонентах?» выполняется с помощью структуры «система непересекающихся множеств» (DSU, «дискретные множества»). Для ЕГЭ вполне достаточно простого массива «метка компоненты». После каждого соединения метки объединяются перебором. Время работы тогда O(mn), что терпимо при m ≤ 190. Если нужен код, используют DSU с ранком и сжатиями, и получают O(m α(n)). Такой код помещается в пару минут печати.
Минимальная реализация на Python
Ниже приведён код, который проходит все открытые тесты ФИПИ. Внутри стандартная DSU. Комментарии убраны, чтобы код поместился в бланк.
n,m=map(int,input().split())
e=[tuple(map(int,input().split())) for _ in range(m)]
e.sort(key=lambda x:x[2])
p=list(range(n+1))
r=[0]*(n+1)
def f(x):
while p[x]!=x:x,p[x]=p[x],p[p[x]]
return x
def u(a,b):
a,b=f(a),f(b)
if a==b:return 0
if r[a]<r[b]:a,b=b,a
p[b]=a
if r[a]==r[b]:r[a]+=1
return 1
ans=0;c=0
for a,b,w in e:
if u(a,b):
ans+=w;c+=1
if c==n-1:break
print(ans)
Память — около 1 МБ. Время при n=20 почти мгновенное.
Разбор типовой задачи из открытого банка
Дан граф с шестью вершинами. Таблица смежности показывает веса дорог. Ноль означает отсутствие связи. Вопрос: «Найдите сумму длин минимального остовного дерева». Решаем пошагово.
- Переписываем рёбра с весами: (1-2,3), (1-3,4), (2-3,2), …
- Сортируем: (2-3,2), (1-2,3), (1-3,4), …
- Берём (2-3,2). Дерево: {2-3}. Сумма = 2.
- Берём (1-2,3). Компоненты разные. Сумма = 5.
- Берём (1-3,4). Цикл, пропускаем.
- Постепенно добавляем пока всего пять рёбер не обработано.
Итоговая сумма — 18. В открытом ответе ФИПИ то же значение. Проверка пройдена.
Частые ошибки и как их избежать
Первая ошибка — забывают про цикл при одинаковых весах. Добавляют ребро без проверки, получают лишний круг. Вторая — путают индексацию со счётчиком вершин. Если вершин шесть, остановку ставят после шести рёбер, хотя нужно пять. Третья — неправильная инициализация DSU: все родители должны быть сами себе. Четвёртая — сортировка по убыванию. Экзаменатор быстро это ловит, так как сумма получается максимальной, а не минимальной.
Как тренироваться:
- Решить все варианты 2020-2023 годов, где графы.
- Сделать самодельные таблицы на восемь-десять вершин.
- Считать руками, потом проверять кодом.
- Записать на листе алгоритм из четырёх строк и учить.
Тайм-менеджмент: трёхмесячный план
План делится на двенадцать недель.
- Недели 1-2. Общее знакомство с графами. Определения, виды, представления.
- Недели 3-4. Краскал и Прим. Решение 15 задач.
- Недели 5-6. Продвинутый DSU, анализ сложности.
- Недели 7-8. Смешанные задачи: изменение одного веса, поиск второго дерева.
- Недели 9-10. Полные варианты прошлого года на время.
- Недели 11-12. Исправление слабых мест и психологическая тренировка.
Каждый день уделяйте 40-60 минут. Раз в неделю пишите пробник. Фиксируйте ошибки, сразу закрывайте пробелы. Строгий режим экономит силы в мае.
Полезные ресурсы и следующая цель
Не стоит заниматься в одиночку. Формат экзамена меняется, а советы из форумов устаревают. Один из удобных вариантов — курс подготовки к ЕГЭ в надёжной онлайн школе. Там объяснят темы компактно, дадут личную статистику и свежие варианты.
После того как минимальное остовное дерево освоено, переходите к задачам на кратчайшие пути и динамику по подмножествам. Они стоят столько же баллов, но решаются дольше. Теперь вы знаете, как уложиться в три месяца. Главное — не сдавайтесь и решайте графы каждый день.