Деревья и алгоритмы: остовное дерево, Краскал и Прим

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

Дерево: связность без излишеств#

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

• рёбер ровно $n-1$ — ровно столько, сколько нужно для связности
• между любыми двумя вершинами существует единственный простой путь
• добавление любого нового ребра создаёт ровно один цикл
• удаление любого ребра разрывает связность — в дереве нет лишних рёбер
• граф связный и ациклический одновременно

Из-за этих свойств дерево называют минимально связным графом. Ловушка здесь обратная: формула $n-1$ — необходимое, но не достаточное условие. Возьмите треугольник 1-2-3 и отдельную цепочку 4-5-6: шесть вершин, пять рёбер — $n-1$ сходится, а дерева нет: есть цикл и нет связности. Число рёбер проверяется всегда в паре со связностью или отсутствием циклов.

Вершина степени 1 в дереве — лист. У всякого дерева с $n\ge 2$ вершинами есть хотя бы два листа — иначе маршрут по рёбрам застрянет. Если выбрать корневую вершину и ориентировать рёбра «от корня», получится корневое дерево: у вершин появляются родители, дети и высота — максимальная длина пути от корня до листа. Так устроены дерево каталогов, DOM-страница и двоичное дерево поиска.

Остовное дерево и минимальность#

Возьмём связный граф и оставим в нём достаточно рёбер, чтобы связность сохранилась, а циклы исчезли. Получится остовное дерево (остов) — подграф, содержащий все вершины и являющийся деревом, то есть ровно $n-1$ ребро. У графа обычно много остовов — вопрос в том, какой из них дешевле.

Модель из жизни: офисы надо соединить сетевым кабелем. Между парами зданий известна стоимость прокладки ($e$ — вес ребра), соединять нужно так, чтобы любые два офиса были связаны, а денег ушло минимум. Формально: найти остов с минимальной суммой весов — минимальное остовное дерево (MST). Если все веса различны, MST единственно; при повторяющихся весах решений может быть несколько, но минимальная стоимость одна.

Алгоритм Краскала: жадность по рёбрам#

Краскал решает MST жадно — и жадность здесь не грубость, а доказуемо верная стратегия. План:

1. 1
   Отсортируйте все рёбра по возрастанию веса.
2. 2
   Идите по списку и добавляйте ребро в ответ, если оно не создаёт цикл с уже взятыми.
3. 3
   Пропускайте рёбра, которые соединяют вершины из одной компоненты.
4. 4
   Остановитесь, когда взято $n-1$ ребро.

Проверка цикла делается структурой union-find (системы непересекающихся множеств): две вершины в одной «семье» — ребро между ними даст цикл. Итоговая сложность $O(m\log m)$, где $m$ — число рёбер; почти всё время уходит на сортировку. Почему жадность не подводит — это теорема (обменный аргумент), но почувствовать её можно: самое дешёвое ребро всегда выгодно взять, если оно не зацикливает.

Алгоритм Прима: жадность от вершины#

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

Проверим Примом на том же графе, старт с $A$: соседи A — B(1) и C(2), берём AB. Из дерева {A, B} минимальное внешнее ребро — AC(2). Из {A, B, C} — CD(4) (ребро BC(3) лежит внутри дерева и не считается). Из {A, B, C, D} — DE(5). Итог тот же: $1+2+4+5=12$. Совпадение не случайно: если все веса различны, MST единственно, и любой корректный алгоритм находит его.

Какой алгоритм быстрее? Зависит от плотности графа. Краскал — $O(m\log m)$ — хорош на разреженных графах, где рёбер мало. Прим с бинарной кучей даёт $O(m\log n)$, а на плотных графах простая реализация с массивом работает за $O(n^2)$ и может обгонять кучную. В учебных задачах выбирают тот, который удобнее вручную: Краскал требует сортировки, Прим — аккуратного ведения списка кандидатов.

Где ещё работают деревья#

Деревья — несущая конструкция информатики. Двоичные деревья поиска дают поиск и вставку за $O(\log n)$, кучи (это тоже деревья) питают очередь с приоритетом, которая нужна Дейкстре и Приму, префиксные деревья реализуют автодополнение в поиске, суффиксные деревья решают задачи про строки. Свойство «единственный путь между вершинами» делает деревья идеальными для любых иерархий: подчинённость, классификация, деление отрезков в сортировке слиянием.

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

Пара фактов про счёт деревьев — для любознательных и для вопросов «со звёздочкой». Сколько листьев у полного двоичного дерева высоты 2? Вершины: корень, два ребёнка, четыре внука — всего 7, рёбер 6, листьев 4. А сколько существует различных деревьев на $n$ помеченных вершинах? Ответ даёт формула Кэли: $n^{n-2}$. Для четырёх городов — $4^2=16$ вариантов сети, и задача MST из них выбирает самый дешёвый.

• Дерево = связность + отсутствие циклов; $n-1$ ребро — следствие, а не определение.
• MST: жадность доказуема — в этой задаче, в отличие от коммивояжёра, она не подводит.
• Краскал — сортируй и не зацикливай; Прим — расти и не отрывайся.
• Проверка цикла — union-find; очередь с приоритетом — топливо Прима.
• Число остовов ищи через рёбра вне дерева, а минимальность — пересчётом MST.