Остовное дерево в информатике: алгоритмы и методы

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

Что такое остовное дерево простыми словами

Начнём с понятий. Граф — это набор вершин (точек) и рёбер (линий между ними). Граф называют связным, если из любой вершины можно добраться до любой другой. Деревом называют связный граф без циклов, то есть без замкнутых путей.

Определение. Остовное дерево графа — это подграф связного графа, который содержит все его вершины и является деревом: он связный и не содержит циклов.

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

Пример: треугольник из вершин A, B и C, где каждая вершина соединена с каждой. Если убрать любое одно ребро, получится цепочка из двух рёбер. Все три вершины на месте, цикла нет, граф связный. Значит, это остовное дерево, и у треугольника таких деревьев ровно три.

Небольшое уточнение про название. Слово «остовный» непривычное, поэтому его часто путают и ищут «основное дерево». Такого отдельного термина в теории графов нет: речь почти всегда об остовном дереве, от слова «остов», то есть каркас.

Свойства остовного дерева графа

У любого остовного дерева есть несколько свойств, которые удобно держать в голове при решении задач.

Первое и главное: число рёбер всегда на одно меньше числа вершин. Если в графе n вершин, в его остовном дереве будет ровно n − 1 ребро. Меньше не получится, иначе какая-то вершина окажется отрезанной. Больше тоже нельзя, иначе появится цикл.

Второе: у дерева, в котором хотя бы две вершины, есть минимум две висячие вершины. Висячей называют вершину, у которой степень вершины равна 1, то есть такую, из которой выходит только одно ребро. Это концы веток дерева. Если сложить степени всех вершин дерева, получится 2(n − 1): каждое ребро учитывается дважды, по разу на каждом конце.

Третье: дерево держится на пределе. Если удалить из остовного дерева любое ребро, граф распадётся на две части. Если добавить любое ребро исходного графа, появится ровно один цикл.

Четвёртое: у одного связного графа может быть много разных остовных деревьев. У треугольника их три, у квадрата с четырьмя сторонами — четыре, а у полного графа из четырёх вершин, где каждая соединена с каждой, их уже 16. Для полного графа из n вершин есть готовая формула Кэли: nⁿ⁻².

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

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

Определение. Минимальное остовное дерево — остовное дерево взвешенного графа, у которого сумма весов рёбер минимально возможная.

Вернёмся к посёлкам. Пусть их пять: A, B, C, D, E. Стоимость кабеля между ними (в миллионах рублей) такая: A–B = 1, B–C = 2, C–D = 3, A–C = 4, B–D = 5, C–E = 6, D–E = 7. Остовных деревьев у этого графа много, и все они связывают пять посёлков четырьмя кабелями. Но стоимость у них разная. Например, дерево из рёбер A–C, C–D, B–D и D–E стоит 4 + 3 + 5 + 7 = 19 миллионов. Задача — найти самый дешёвый вариант. Если все веса рёбер разные, как в нашем примере, минимальное дерево будет единственным, и любой правильный алгоритм найдёт именно его.

Перебирать все деревья вручную бессмысленно: на полном графе из сотни вершин их больше, чем атомов во Вселенной. Поэтому придумали алгоритмы, которые находят минимальное остовное дерево за разумное время. Главных три: Крускала, Прима и Борувки. Прогоним каждый на нашем примере.

Алгоритм Крускала: как работает

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

Порядок действий такой.

1. Отсортировать все рёбра по весу от меньшего к большему.
2. Взять очередное ребро из списка.
3. Если оно соединяет вершины, которые ещё не связаны между собой, добавить его в дерево. Если связаны, пропустить: иначе появится цикл.
4. Повторять, пока в дереве не окажется n − 1 ребро.

На примере с посёлками. После сортировки рёбер получаем: A–B (1), B–C (2), C–D (3), A–C (4), B–D (5), C–E (6), D–E (7). Берём A–B, B–C и C–D. Ребро A–C пропускаем: A и C уже связаны через B. Ребро B–D тоже пропускаем. Берём C–E, и в дереве уже четыре ребра. Итоговая стоимость: 1 + 2 + 3 + 6 = 12 миллионов.

Самая затратная часть — сортировка, поэтому сложность алгоритма оценивают как O(E log E), где E — число рёбер. Алгоритм Крускала особенно хорош на разреженных графах, где рёбер немного. Чтобы быстро проверять, не создаст ли ребро цикл, в программировании используют структуру Union-Find («объединение — поиск»), но для решения на бумаге достаточно следить, какие вершины уже связаны.

Алгоритм Прима: как работает

Алгоритм Прима действует иначе: дерево растёт из одной стартовой вершины, как снежный ком.

1. Выбрать любую стартовую вершину.
2. Среди всех рёбер, которые ведут из уже построенного дерева к ещё не включённым вершинам, выбрать ребро минимального веса.
3. Добавить это ребро и новую вершину в дерево.
4. Повторять, пока в дереве не окажутся все вершины.

Стартуем из A. Из неё ведут A–B (1) и A–C (4): берём A–B. Теперь дерево {A, B}, самое дешёвое ребро наружу — B–C (2). Из {A, B, C} самое дешёвое ребро к новой вершине — C–D (3). Остался посёлок E: к нему ведут C–E (6) и D–E (7), берём C–E. Итог тот же: 12 миллионов. Обрати внимание: ребро A–C (4) алгоритм Прима так и не взял, потому что к моменту, когда оно стало бы выгодным, вершина C уже была в дереве.

Алгоритм Прима особенно эффективен на плотных графах, где рёбер много. Если хранить граф в виде матрицы смежности, простая реализация работает за O(V²), где V — число вершин, и это выгодно, когда рёбер почти столько же, сколько пар вершин. Для разреженных графов используют версию с приоритетной очередью (кучей): она работает за O(E log V). Так что один и тот же алгоритм Прима в разных реализациях подходит под разные графы.

Чем алгоритм Прима отличается от алгоритма Крускала

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

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

Алгоритм Прима растит одно дерево из одной точки. В любой момент построенная часть связная, а новые рёбра всегда примыкают к ней.

Отсюда и практический выбор. Если рёбер мало и их легко отсортировать, удобнее Крускал. Если граф плотный и задан матрицей, быстрее будет Прим. Итоговый минимальный вес у обоих совпадает. Сами деревья тоже совпадут, если все веса рёбер разные. Если же есть рёбра с одинаковым весом, алгоритмы могут вернуть разные деревья с одинаковой суммой.

Алгоритм Борувки: ещё один способ

Этот алгоритм старше двух других: чешский математик Отакар Борувка описал его в 1926 году, когда проектировал электросеть для Моравии.

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

В нашем примере всё решается за один шаг. Самые дешёвые рёбра: у A и B — A–B (1), у C — B–C (2), у D — C–D (3), у E — C–E (6). Добавляем их и сразу получаем то же дерево весом 12.

За каждый шаг число компонент уменьшается как минимум вдвое, поэтому шагов нужно не больше log₂V. Главный плюс алгоритма Борувки в том, что компоненты ищут свои рёбра независимо друг от друга. Такую работу легко раздать нескольким процессорам сразу, поэтому алгоритм хорошо подходит для параллельных и распределённых вычислений.

Где применяются остовные деревья на практике

Задача про посёлки — не выдумка учебника. Минимальное остовное дерево решает реальные инженерные задачи.

• Сети связи и электросети. Проложить кабель или линию электропередачи так, чтобы подключить все объекты с минимальными затратами.
• Транспортная инфраструктура. Спланировать минимальный набор дорог или трубопроводов между городами.
• Разводка электронных схем. Соединить контакты на плате проводниками минимальной общей длины.
• Кластеризация данных. Строят минимальное остовное дерево по точкам данных, затем удаляют самые длинные рёбра. Оставшиеся куски дерева и есть группы похожих объектов.
• Маршруты доставки. Минимальное остовное дерево используют как основу для приближённого решения задачи коммивояжёра: найти короткий маршрут через все точки. Точного ответа это не даёт, зато работает быстро.

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

Остовное дерево и просто дерево: в чём разница

Эти понятия легко перепутать, потому что остовное дерево — тоже дерево. Разница в том, откуда оно берётся.

Дерево — самостоятельная структура. Это любой связный граф без циклов, и ему не нужен никакой исходный граф. Папки с файлами на компьютере, генеалогическое дерево, турнирная сетка — всё это деревья сами по себе.

Остовное дерево существует только относительно конкретного графа. Это дерево, выделенное из графа как подграф и содержащее все его вершины. Одно и то же дерево может быть остовным для одного графа и не быть им для другого, например, если в другом графе есть вершины, которые в дерево не вошли. Бывает и наоборот: в дереве есть ребро, которого нет в графе. Тогда это дерево вообще не подграф, и остовным для этого графа оно быть не может, даже если вершины совпадают.

Удобная проверка: если тебя спрашивают про остовное дерево, всегда уточняй, о каком графе речь, и сверяй число вершин. Если про дерево вообще — достаточно проверить связность и отсутствие циклов.

Заключение

Остовное дерево связывает все вершины графа без лишних рёбер, а Крускал, Прим и Борувка находят минимальное дерево разными путями с одним итогом. Нарисуй граф из 5–6 вершин с весами и прогони на нём Крускала, а затем Прима: если суммы совпали, ты всё сделал правильно.

Совет от Сотки: графы есть и на экзаменах: в ЕГЭ по информатике — задание 1 (сопоставить граф с таблицей), в ОГЭ — задание 4 (кратчайший путь). Рисуй граф на черновике, даже если он кажется простым.

Теория графов, кстати, началась с задачи о кёнигсбергских мостах, которую в 1736 году решил Леонард Эйлер, автор кругов из задания 8 ОГЭ по информатике. Разобрать графы на экзаменных задачах поможет бесплатное занятие по подготовке к ЕГЭ по информатике на платформе Сотка, а логику потренируй на разборе задания 2 ЕГЭ.

Частые вопросы об остовных деревьях (FAQ)

Может ли у графа быть только одно остовное дерево?

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

«Основное дерево» и «остовное дерево» — это одно и то же?

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

Какой алгоритм построения остовного дерева выбрать на практике?

Для разреженных графов, заданных списком рёбер, обычно берут алгоритм Крускала. Для плотных графов, заданных матрицей смежности, удобнее алгоритм Прима. Алгоритм Борувки выбирают, когда вычисления нужно распараллелить на много процессоров. На небольших учебных графах подойдёт любой: ответ по весу будет одинаковым.

Есть ли остовное дерево у несвязного графа?

Нет. Дерево по определению связное, а в несвязном графе часть вершин недостижима из других. Вместо дерева у такого графа строят остовный лес: отдельное остовное дерево для каждой компоненты связности. Алгоритм Крускала, запущенный на несвязном графе, как раз и выдаст такой лес.

Проверь себя

1. Сколько рёбер в остовном дереве графа из 10 вершин?

• а) 10 — нет, при 10 рёбрах на 10 вершинах обязательно появится цикл.
• б) 9 — верно, в дереве рёбер всегда на одно меньше, чем вершин.
• в) Зависит от числа рёбер исходного графа — нет, у любого остовного дерева графа из n вершин ровно n − 1 ребро.

2. Какой из подграфов квадрата ABCD (рёбра AB, BC, CD, DA) является его остовным деревом?

• а) Рёбра AB, BC, CD — верно, все четыре вершины связаны, а цикла нет.
• б) Рёбра AB и CD — нет, получится два отдельных куска, граф несвязный.
• в) Рёбра AB, BC, CD, DA — нет, это исходный квадрат с циклом, а в дереве циклов быть не должно.

3. Граф с рёбрами A–B (2), A–C (3), B–C (1), C–D (4), B–D (5). Какой вес у минимального остовного дерева?

• а) 6 — нет, так получится, если взять только рёбра 1, 2 и 3: вершина D остаётся неподключённой.
• б) 7 — верно: алгоритм Крускала берёт B–C (1), A–B (2), пропускает A–C (3), потому что A и C уже связаны, и добавляет C–D (4). Итого 1 + 2 + 4 = 7.
• в) 10 — нет, это сумма рёбер B–C, C–D и B–D: они образуют цикл и не подключают вершину A.