Минимальное остовное дерево 🌲
В прошлом уроке ты искал кратчайшие пути между всеми парами вершин взвешенного графа — задачу «как добраться из точки A в точку B максимально дёшево». Этот урок ставит другой вопрос: как связать все вершины графа между собой одновременно, потратив на это как можно меньше суммарных ресурсов, и не создав при этом ни одного лишнего, избыточного соединения. Разница принципиальная: кратчайший путь — это оптимизация одной конкретной пары точек, минимальное остовное дерево — это оптимизация всей структуры связей сразу, целиком.
Представь, что телекоммуникационная компания должна проложить оптоволоконный кабель между 500 населённых пунктов так, чтобы от любого из них можно было добраться до любого другого (напрямую или через промежуточные точки), а суммарная длина проложенного кабеля — то есть суммарные затраты на прокладку — была минимальной. Никто не требует, чтобы путь между двумя конкретными городами был кратчайшим из всех возможных, — требуется только связность всей сети целиком при минимальных совокупных вложениях. Это ровно задача о минимальном остовном дереве (minimum spanning tree, MST), и она возникает не только в прокладке кабелей: в проектировании дорожных и электрических сетей, в разводке печатных плат, в построении приближённых решений для задачи коммивояжёра, в сегментации изображений — и, что особенно важно для тебя как будущего специалиста по данным, в одном из самых распространённых методов иерархической кластеризации.
Здесь стоит сразу провести ту связь, ради которой этот урок особенно важен на курсе по машинному обучению. Метод одиночной связи (single linkage), один из классических способов построения иерархической кластеризации, на каждом шаге объединяет два кластера, между которыми находится пара ближайших точек. Если формализовать эту процедуру целиком — воспринимать точки данных как вершины полного графа, а расстояние между ними как вес ребра, — то последовательность объединений кластеров методом одиночной связи в точности совпадает с порядком, в котором рёбра добавляются в минимальное остовное дерево алгоритмом Крускала. Дендрограмма, которую ты видел или ещё увидишь при изучении кластеризации, — это, по сути, визуализация MST с явным порядком, в котором рёбра «включались» в структуру. Понимание MST на алгоритмическом уровне — это не абстрактное упражнение по теории графов, а прямой ключ к пониманию того, что происходит внутри одного из базовых инструментов обучения без учителя (unsupervised learning).
В этом уроке ты разберёшься, что формально означает «остовное дерево» и «минимальное остовное дерево», изучишь два классических жадных алгоритма его построения — алгоритм Прима, который выращивает дерево постепенно от одной стартовой вершины, и алгоритм Крускала, который жадно сортирует и перебирает все рёбра графа, опираясь на структуру данных «система непересекающихся множеств» (Union-Find). Ты увидишь, что оба алгоритма, несмотря на совершенно разную логику работы, для одного и того же графа с попарно различными весами рёбер всегда дают один и тот же результат — и поймёшь, почему это не совпадение, а математическая гарантия жадного подхода к этой конкретной задаче.
История: от электрификации Моравии до Bell Labs
Первый известный алгоритм построения минимального остовного дерева появился значительно раньше, чем сложилась современная теория алгоритмов как отдельная дисциплина. В 1926 году чешский математик Отакар Борувка опубликовал работу, в которой решал вполне практическую инженерную задачу: как максимально экономно электрифицировать Моравию (историческую область на территории современной Чехии), соединив населённые пункты сетью линий электропередачи с минимальными суммарными затратами на провода. Алгоритм Борувки устроен иначе, чем алгоритмы Прима и Крускала, которые будут в центре этого урока: он работает параллельно сразу для всех компонент дерева, на каждом шаге (раунде) для каждого текущего фрагмента дерева находя минимальное ребро, выходящее наружу, и присоединяя его — так что за один раунд число фрагментов может уменьшаться сразу в несколько раз. Это делает алгоритм Борувки естественно параллелизуемым, и по этой причине он снова стал актуален спустя почти сто лет — в задачах построения MST на гигантских графах, распределённых по множеству вычислительных узлов.
Идея, которую сегодня чаще всего называют алгоритмом Прима, тоже возникла не единожды и не в порядке, который подсказывает её общепринятое название. В 1930 году чешский математик Войтех Ярник независимо от Борувки предложил алгоритм, который постепенно наращивает единое дерево от одной стартовой вершины, на каждом шаге добавляя минимальное ребро, соединяющее уже построенную часть с новой вершиной, — именно эта идея разбирается ниже как «алгоритм Прима». Однако работа Ярника была опубликована на чешском языке и десятилетиями оставалась практически неизвестной за пределами Чехословакии. В 1957 году американский математик и информатик из Bell Labs Роберт Прим независимо переоткрыл ту же идею и опубликовал её на английском языке в Bell System Technical Journal — именно эта публикация принесла алгоритму мировую известность и имя, под которым он изучается сегодня. Отдать должное первооткрывателю принято двойным названием — алгоритм Ярника — Прима, — хотя в большинстве учебников и курсов, включая этот, закрепилось более короткое «алгоритм Прима».
Алгоритм, который сегодня носит имя Джозефа Крускала, формально был опубликован раньше алгоритма Прима — в 1956 году, всего годом позже переоткрытия Дейкстрой похожей идеи для кратчайших путей. Крускал, работавший в той же Bell Labs, предложил принципиально иную стратегию: не выращивать дерево постепенно от одной вершины, а сразу рассмотреть все рёбра графа, отсортировать их по весу и жадно добавлять каждое следующее по возрастанию, если оно не создаёт цикл с уже добавленными. Обе идеи — Прима и Крускала — оказались настолько устойчивыми и настолько разными по внутренней логике, что вошли в канон алгоритмов на графах как два взаимодополняющих, но принципиально разных способа решения одной и той же задачи, и оба преподаются до сих пор бок о бок, потому что каждый из них лучше подходит для своего сценария применения — об этом отдельно пойдёт речь в разделе про сравнение.
Что такое остовное дерево и минимальное остовное дерево
Интуиция
Возьми взвешенный связный граф — набор вершин, соединённых рёбрами, у каждого из которых есть числовая «стоимость» (расстояние, цена прокладки кабеля, время передачи данных). Задача — выбрать среди всех рёбер этого графа подмножество, которое, во-первых, соединяет все вершины между собой (от любой вершины до любой другой можно добраться по выбранным рёбрам), а во-вторых, не содержит ни одного лишнего ребра — если убрать любое из выбранных рёбер, граф на выбранном подмножестве распадётся на несвязные части. Структура, обладающая двумя этими свойствами одновременно (связность плюс отсутствие лишних рёбер), — это дерево в строгом графовом смысле: связный граф без циклов. Поскольку это дерево «натянуто» на все вершины исходного графа, как ткань на каркас, его называют остовным (или каркасным, spanning tree).
У одного и того же графа обычно существует много разных остовных деревьев — можно выбирать разные подмножества рёбер, лишь бы результат оставался связным деревом без циклов. Минимальное остовное дерево — это то из них (может быть, не единственное), для которого сумма весов входящих в него рёбер минимальна среди всех возможных остовных деревьев данного графа.
Формальное определение
Определение. Пусть $G = (V, E)$ — связный неориентированный взвешенный граф с множеством вершин $V$, множеством рёбер $E$ и функцией веса $w: E \to \mathbb{R}$. Остовным деревом графа $G$ называется подграф $T = (V, E_T)$, где $E_T \subseteq E$, такой что $T$ связен и не содержит циклов. Минимальным остовным деревом (MST) называется остовное дерево $T^*$, для которого суммарный вес рёбер $w(T^*) = \sum_{e \in E_T} w(e)$ минимален среди всех возможных остовных деревьев графа $G$.
Из этого определения сразу следует важное структурное свойство: любое остовное дерево графа с $n$ вершинами содержит ровно $n - 1$ ребро — не больше и не меньше. Не больше, потому что дерево по определению не содержит циклов, а граф с $n$ вершинами и более чем $n-1$ рёбрами обязательно содержит хотя бы один цикл. Не меньше, потому что связный граф с $n$ вершинами не может иметь меньше $n-1$ ребра — иначе он неизбежно распадается хотя бы на две несвязные компоненты. Это простое наблюдение — надёжный инструмент самопроверки: если после построения MST у тебя получилось не ровно $n-1$ ребро, значит, где-то в построении есть ошибка.
Отдельно стоит подчеркнуть: минимальное остовное дерево не обязано быть единственным. Если в графе есть несколько рёбер с одинаковым весом, вполне может существовать несколько разных наборов рёбер, дающих одну и ту же минимальную суммарную стоимость. Единственность гарантируется только тогда, когда все веса рёбер графа попарно различны, — этот факт пригодится при доказательстве корректности жадных алгоритмов ниже.
Примеры с разбором
Пример 1. Остовное дерево простого треугольника. Дан граф из трёх вершин $A, B, C$ с рёбрами $AB$ веса $3$, $BC$ веса $5$, $AC$ веса $7$ — то есть треугольник, где выбраны все три возможных ребра. У этого графа три разных остовных дерева, каждое из которых получается удалением ровно одного ребра (иначе граф либо остаётся с циклом, либо теряет связность): дерево $\{AB, BC\}$ весом $3+5=8$, дерево $\{AB, AC\}$ весом $3+7=10$, дерево $\{BC, AC\}$ весом $5+7=12$. Минимальный вес среди них — $8$, у дерева $\{AB, BC\}$, то есть минимальное остовное дерево получается удалением самого тяжёлого ребра треугольника ($AC$, вес $7$). Это иллюстрирует общее наблюдение: удаление самого тяжёлого ребра любого цикла графа никогда не может ухудшить (сделать более дорогим) минимальное остовное дерево — это ребро заведомо избыточно для связности при наличии более дешёвой альтернативы через оставшиеся вершины цикла.
Пример 2. Неединственность MST при равных весах. Дан граф из четырёх вершин $A, B, C, D$, образующих цикл: рёбра $AB$ веса $2$, $BC$ веса $2$, $CD$ веса $2$, $DA$ веса $5$. Три ребра цикла имеют одинаковый минимальный вес $2$. Любое остовное дерево этого графа получается удалением одного ребра из цикла. Удаление ребра $DA$ (веса $5$) даёт дерево $\{AB, BC, CD\}$ суммарным весом $6$ — это минимум. Но что, если вместо этого удалить, скажем, ребро $AB$? Тогда получившийся набор $\{BC, CD, DA\}$ уже не связывает вершину $A$ ни с чем, кроме как через $D$, и его вес $2+2+5=9$ — заведомо хуже. В этом примере минимальное остовное дерево на самом деле единственно (нужно удалить именно $DA$), но если бы, например, веса были $AB=2, BC=2, CD=2, DA=2$ (то есть все четыре ребра равны), то любое из четырёх возможных остовных деревьев (получаемых удалением любого одного ребра) имело бы одинаковый суммарный вес $6$ — и все четыре были бы равноправными минимальными остовными деревьями одновременно. Это ровно тот случай неединственности, о котором говорилось в формальном определении.
Пример 3. Сколько вообще существует остовных деревьев. Формула Кэли утверждает, что полный граф на $n$ вершинах (граф, где каждая пара вершин соединена ребром) имеет ровно $n^{n-2}$ различных остовных деревьев. Для $n=4$ вершин это $4^{2}=16$ различных остовных деревьев, для $n=10$ — уже $10^{8}=100\,000\,000$, а для $n=100$ — астрономическое число с почти двумя сотнями цифр. Это наблюдение — не праздная арифметика, а прямое объяснение, почему задачу о минимальном остовном дереве нельзя решать полным перебором всех возможных остовных деревьев, вычисляя суммарный вес каждого и выбирая наименьший: уже на графах умеренного размера число вариантов взрывается быстрее, чем любой современный компьютер способен перебрать за разумное время. Именно поэтому алгоритмы Прима и Крускала, о которых пойдёт речь дальше, ценны не просто как «ещё один способ» решения задачи — они единственный практически реализуемый способ.
Почему это важно. Различие между «остовным деревом» вообще и «минимальным остовным деревом» — это различие между произвольным работающим решением и оптимальным решением, и цена этого различия в реальных задачах измеряется вполне конкретными деньгами: если сеть кабелей связывает все города, но не оптимальным образом, компания переплачивает за лишнюю длину провода — иногда в разы. Формула Кэли, в свою очередь, объясняет, почему для решения этой задачи нужны не наивные, а специально сконструированные жадные алгоритмы, которые находят оптимум, не перебирая экспоненциальное число вариантов.
Алгоритм Прима: жадный рост дерева от одной вершины
Интуиция
Алгоритм Прима решает задачу способом, который интуитивно похож на то, как растёт кристалл или как расширяется территория при завоевании: начинаем с одной-единственной вершины, объявляем её «уже частью дерева», а дальше на каждом шаге смотрим на все рёбра, которые ведут из уже построенной части дерева наружу — к вершинам, ещё не включённым в дерево, — и жадно выбираем среди них ребро с минимальным весом. Выбранное ребро и вершина, к которой оно ведёт, присоединяются к дереву, и процесс повторяется заново: снова смотрим на рёбра, ведущие из (уже увеличившейся) построенной части наружу, снова выбираем минимальное. Дерево растёт как единый связный кусок — никогда не распадаясь на несколько фрагментов, — пока не охватит все вершины графа.
Ключевая деталь, которую легко упустить: на каждом шаге сравниваются не все рёбра графа, а только те, что идут от текущего дерева к вершинам за его пределами (это множество рёбер иногда называют «границей» дерева). Ребро, соединяющее две вершины, уже находящиеся внутри дерева, никогда не рассматривается как кандидат — оно неизбежно создало бы цикл.
Алгоритм
Алгоритм Прима.
- Выбрать произвольную стартовую вершину $s \in V$; включить её в дерево $T$, все остальные вершины считать «вне дерева».
- Пока в дерево $T$ включены не все вершины графа:
- среди всех рёбер, соединяющих вершину внутри $T$ с вершиной вне $T$, найти ребро $(u, v)$ минимального веса;
- добавить ребро $(u, v)$ и вершину $v$ (ту из концов ребра, что была вне $T$) в дерево $T$.
- Вернуть $T$ — построенное дерево содержит $n-1$ ребро и является минимальным остовным деревом графа.
На практике шаг «найти минимальное ребро на границе» реализуется эффективно с помощью приоритетной очереди (бинарной кучи): для каждой вершины вне дерева хранится минимальный известный вес ребра, связывающего её с деревом, и на каждой итерации из кучи извлекается вершина с минимальным таким весом — точно так же, как в алгоритме Дейкстры извлекалась вершина с минимальным предварительным расстоянием. Это не случайное сходство: оба алгоритма относятся к одному и тому же семейству «жадных алгоритмов роста от источника» и почти идентичны по структуре кода, различаясь только тем, какая величина минимизируется на каждом шаге (в Дейкстре — накопленное расстояние от старта, в Приме — вес одного-единственного ребра, ведущего к новой вершине).
Примеры с разбором
Пример 1. Полная трассировка на графе из шести вершин. Дан граф с вершинами $A, B, C, D, E, F$ и рёбрами: $AB=4$, $AC=2$, $BC=1$, $BD=5$, $CD=8$, $CE=10$, $DE=2$, $DF=6$, $EF=3$. Запустим алгоритм Прима со стартовой вершиной $A$.
Шаг 0. Дерево: {A}
Граничные рёбра: A-B (4), A-C (2)
Минимальное: A-C (2) → добавляем C
Шаг 1. Дерево: {A, C}
Граничные рёбра: A-B (4), C-B (1), C-D (8), C-E (10)
Минимальное: C-B (1) → добавляем B
Шаг 2. Дерево: {A, B, C}
Граничные рёбра: B-D (5), C-D (8), C-E (10)
(ребро A-B уже внутри дерева, больше не рассматривается)
Минимальное: B-D (5) → добавляем D
Шаг 3. Дерево: {A, B, C, D}
Граничные рёбра: D-E (2), D-F (6), C-E (10)
Минимальное: D-E (2) → добавляем E
Шаг 4. Дерево: {A, B, C, D, E}
Граничные рёбра: E-F (3), D-F (6)
Минимальное: E-F (3) → добавляем F
Шаг 5. Дерево: {A, B, C, D, E, F} — все вершины включены, останавливаемся
Итоговое MST состоит из рёбер $AC(2), BC(1), BD(5), DE(2), EF(3)$, суммарный вес $2+1+5+2+3=13$. Ровно $5=6-1$ рёбер, как и требует свойство остовного дерева.
Пример 2. Влияние выбора стартовой вершины. Важное свойство алгоритма Прима: результат (итоговое MST и его суммарный вес) не зависит от того, с какой вершины начат рост дерева, — при условии, что граф связен. Запусти алгоритм Прима на том же графе из примера 1, но стартуя с вершины $F$: на первом шаге единственное граничное ребро — $EF(3)$ (или $DF(6)$, но $EF$ меньше), добавляется $E$; далее граничные рёбра $DE(2)$ и $CE(10)$ — минимальное $DE(2)$, добавляется $D$; далее $BD(5)$ и $CD(8)$ — минимальное $BD(5)$, добавляется $B$; далее $AB(4)$ и $BC(1)$ — минимальное $BC(1)$, добавляется $C$; далее $AC(2)$ — добавляется $A$. Получившееся дерево — те же самые рёбра $\{EF, DE, BD, BC, AC\}$, суммарный вес снова $13$. Разный порядок добавления вершин, но тот же итоговый набор рёбер — потому что при попарно различных весах MST этого графа единственно, и любой корректный жадный алгоритм обязан к нему прийти, независимо от точки старта.
Пример 3. Реализация с приоритетной очередью и оценка сложности.
import heapq
def prim_mst(graph, start):
# graph: словарь {вершина: [(сосед, вес), ...]}
visited = {start}
mst_edges = []
total_weight = 0
# в кучу кладём (вес, откуда, куда) для всех рёбер из start
heap = [(w, start, v) for v, w in graph[start]]
heapq.heapify(heap)
while heap and len(visited) < len(graph):
weight, u, v = heapq.heappop(heap)
if v in visited:
continue # ребро ведёт внутрь дерева — пропускаем
visited.add(v)
mst_edges.append((u, v, weight))
total_weight += weight
for to, w in graph[v]:
if to not in visited:
heapq.heappush(heap, (w, v, to))
return mst_edges, total_weight
При использовании бинарной кучи каждая вершина попадает в очередь не более $\deg(v)$ раз (по разу на каждое инцидентное ребро в худшем случае), а операции с кучей стоят $O(\log E)$, что для простого графа сопоставимо с $O(\log V)$. Итоговая временная сложность — $O(E \log V)$, где $E$ — число рёбер, $V$ — число вершин. Если вместо кучи использовать плотную матрицу смежности и линейный поиск минимума среди граничных рёбер на каждом шаге, получится $O(V^2)$ — асимптотически хуже на разреженных графах, но проще по константе и предпочтительнее, когда граф плотный (об этом отдельно в разделе про сравнение).
Почему это важно
Алгоритм Прима особенно удобен, когда граф задан не явным списком рёбер, а неявно — например, когда «соседей» вершины приходится вычислять на лету (координаты точек на плоскости, где ребро между любыми двумя точками существует с весом, равным расстоянию, но явно хранить все $O(n^2)$ рёбер невыгодно). Поскольку алгоритм Прима на каждом шаге работает только с границей уже построенного дерева, а не со всем множеством рёбер сразу, он органично подходит для таких «графов без явного списка рёбер» и для плотных графов, где число рёбер приближается к $O(V^2)$, — в этом случае сложность $O(V^2)$ через простую матрицу смежности оказывается ничуть не хуже (а по константе — даже лучше) сложности $O(E\log V)$ через кучу, потому что $E$ здесь и так порядка $V^2$.
Алгоритм Крускала: жадная сортировка рёбер и Union-Find
Интуиция
Если алгоритм Прима похож на растущий из одной точки кристалл, то алгоритм Крускала устроен принципиально иначе: он не начинает с одной вершины и не поддерживает единое связное дерево на протяжении всего процесса. Вместо этого он с самого начала смотрит на все рёбра графа сразу, сортирует их по возрастанию веса, а затем проходит по этому отсортированному списку от самого дешёвого ребра к самому дорогому и жадно решает по каждому ребру: включать его в итоговый набор или нет. Критерий включения предельно прост — ребро включается тогда и только тогда, когда его концы принадлежат разным, ещё не соединённым между собой частям (компонентам) уже построенного «леса» из рёбер. Если оба конца ребра уже лежат в одной компоненте, добавление этого ребра создало бы цикл — а циклы в дереве, как ты помнишь из формального определения, запрещены категорически.
В отличие от алгоритма Прима, на промежуточных шагах алгоритма Крускала построенная структура — это не одно связное дерево, а лес: несколько отдельных деревьев-компонент, которые постепенно сливаются друг с другом по мере обработки всё более дорогих рёбер, пока к концу процесса весь лес не сольётся в одно-единственное дерево, охватывающее все вершины графа.
Алгоритм
Алгоритм Крускала.
- Отсортировать все рёбра графа $E$ по неубыванию веса.
- Инициализировать структуру «система непересекающихся множеств» так, чтобы каждая вершина изначально была отдельным множеством (компонентой).
- Для каждого ребра $(u, v)$ в отсортированном порядке:
- если $u$ и $v$ принадлежат разным множествам (найти это через операцию
find), добавить ребро $(u, v)$ в результат и объединить множества $u$ и $v$ (операцияunion);- если $u$ и $v$ уже в одном множестве — пропустить ребро (оно создало бы цикл).
- Остановиться, когда добавлено $n-1$ ребро (или когда закончились рёбра). Результат — минимальное остовное дерево.
Union-Find: как быстро проверять, лежат ли две вершины в одной компоненте
Наивная проверка «принадлежат ли $u$ и $v$ одной компоненте» через обход графа обходилась бы слишком дорого, если выполнять её для каждого из $E$ рёбер на каждом шаге. Здесь на помощь приходит специализированная структура данных — система непересекающихся множеств, она же Union-Find, она же disjoint set union (DSU). Идея устройства простая: каждое множество представлено как дерево (в другом, «внутреннем» смысле, не путать с остовным деревом), у каждого элемента хранится ссылка на «родителя», а представителем всего множества считается корень — элемент, который сам себе родитель. Операция find(x) поднимается по ссылкам «родитель» от $x$ до корня и возвращает этот корень; два элемента находятся в одном множестве тогда и только тогда, когда find для них возвращает одинаковый корень. Операция union(x, y) находит корни обоих элементов и «подвешивает» корень одного дерева к корню другого, объединяя два множества в одно.
Наивная реализация Union-Find может выродиться в длинную цепочку (если объединять множества неаккуратно, дерево внутри DSU может стать таким же вытянутым, как несбалансированное BST из предыдущих уроков), и тогда find будет стоить $O(n)$ в худшем случае. Две простые оптимизации решают эту проблему почти полностью. Первая — объединение по рангу (union by rank): при объединении корень менее «высокого» дерева всегда подвешивается под корень более высокого, а не наоборот, — это не даёт высоте результирующего дерева расти быстрее логарифма. Вторая — сжатие пути (path compression): во время выполнения find(x) все узлы, через которые прошёл путь до корня, перепривязываются напрямую к найденному корню, — это делает дерево DSU плоским настолько быстро, что уже следующий find для тех же элементов почти всегда занимает время $O(1)$. При обеих оптимизациях вместе амортизированная сложность одной операции Union-Find становится $O(\alpha(n))$, где $\alpha$ — обратная функция Аккермана, растущая настолько медленно, что для всех практически мыслимых значений $n$ (вплоть до числа атомов во Вселенной) $\alpha(n) \le 5$ — иначе говоря, на практике каждая операция обходится за считаные шаги, фактически как константа.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # сжатие пути
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # уже в одном множестве — цикл
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
Примеры с разбором
Пример 1. Полная трассировка на том же графе из шести вершин. Возьмём тот же граф, что и для алгоритма Прима: $AB=4$, $AC=2$, $BC=1$, $BD=5$, $CD=8$, $CE=10$, $DE=2$, $DF=6$, $EF=3$. Отсортируем рёбра по неубыванию веса: $BC(1)$, $AC(2)$, $DE(2)$, $EF(3)$, $AB(4)$, $BD(5)$, $DF(6)$, $CD(8)$, $CE(10)$.
Множества изначально: {A} {B} {C} {D} {E} {F}
BC (1): B и C в разных множествах → добавляем. {B,C} {A} {D} {E} {F}
AC (2): A и C в разных множествах → добавляем. {A,B,C} {D} {E} {F}
DE (2): D и E в разных множествах → добавляем. {A,B,C} {D,E} {F}
EF (3): E и F в разных множествах → добавляем. {A,B,C} {D,E,F}
AB (4): A и B УЖЕ в одном множестве → создаёт цикл, пропускаем.
BD (5): B в {A,B,C}, D в {D,E,F} — разные множества → добавляем. {A,B,C,D,E,F}
Добавлено 5 рёбер (= 6 - 1), все вершины в одном множестве — останавливаемся.
Итоговое MST — рёбра $BC(1), AC(2), DE(2), EF(3), BD(5)$, суммарный вес $1+2+2+3+5=13$. Это в точности тот же набор рёбер и тот же суммарный вес, что и в трассировке алгоритма Прима из предыдущего раздела, — совпадение неслучайное: при попарно различных весах рёбер минимальное остовное дерево графа единственно, и оба жадных алгоритма, несмотря на кардинально разную внутреннюю логику, гарантированно приходят к нему.
Пример 2. Момент обнаружения цикла и роль Union-Find. В трассировке выше рассмотрим шаг с ребром $AB(4)$ отдельно. На этом шаге вершина $A$ уже была объединена с $B$ и $C$ на предыдущих шагах (через рёбра $BC$ и $AC$) — они все лежат в одном множестве $\{A,B,C\}$ с общим корнем в структуре DSU. Вызов find(A) и find(B) вернёт один и тот же корень, и алгоритм немедленно, без всякого обхода графа, понимает: добавление ребра $AB$ создало бы цикл $A \to C \to B \to A$, — и пропускает это ребро. Без структуры Union-Find для такой проверки пришлось бы каждый раз запускать обход графа (DFS или BFS) от одной вершины до другой в уже построенной части — операция, которая стоила бы $O(V)$ в худшем случае вместо практически константного времени find.
Пример 3. Реализация целиком и оценка сложности.
def kruskal_mst(n, edges):
# edges: список кортежей (вес, u, v)
edges_sorted = sorted(edges) # сортировка — O(E log E)
dsu = DSU(n)
mst_edges = []
total_weight = 0
for weight, u, v in edges_sorted:
if dsu.union(u, v): # union возвращает False при цикле
mst_edges.append((u, v, weight))
total_weight += weight
if len(mst_edges) == n - 1:
break # дерево построено, дальше можно не искать
return mst_edges, total_weight
Сложность алгоритма Крускала определяется в первую очередь сортировкой рёбер: $O(E \log E)$. Поскольку $E$ в простом графе не превышает $O(V^2)$, то $\log E = O(\log V)$, и итоговая асимптотика чаще всего записывается как $O(E \log V)$ — формально та же самая асимптотика, что и у алгоритма Прима с бинарной кучей, хотя структура вычислений совершенно разная. Проход по отсортированному списку рёбер с операциями Union-Find добавляет ещё $O(E \cdot \alpha(V))$, но эта величина практически не влияет на итоговую асимптотику, потому что растёт значительно медленнее, чем стоимость сортировки.
Почему это важно
Алгоритм Крускала особенно удобен, когда граф изначально задан именно списком рёбер (а не списком смежности вершин) — например, когда данные приходят в виде таблицы «откуда, куда, вес», как это часто бывает в реальных наборах данных о связях (список маршрутов, список расстояний между парами точек, список весов сходства между объектами в задаче кластеризации). Поскольку алгоритм с самого начала работает именно со списком рёбер и не требует поддержания единого связного дерева на каждом шаге, он естественно подходит и для разреженных графов, где число рёбер $E$ значительно меньше $V^2$: сортировка сравнительно небольшого списка рёбер обходится дёшево, а Union-Find обеспечивает почти константную стоимость проверки цикла на каждом шаге.
Сравнение алгоритмов и применения MST
Интуиция: нет «лучшего» алгоритма — есть подходящий под структуру графа
Оба алгоритма — и Прима, и Крускала — гарантированно находят минимальное остовное дерево благодаря одному и тому же математическому факту, известному как свойство разреза (cut property): для любого разбиения вершин графа на две непустые части ребро минимального веса, соединяющее эти две части, обязательно входит хотя бы в одно минимальное остовное дерево графа. И Прим, и Крускал на каждом своём шаге, по сути, применяют именно это свойство — просто к разным разрезам: Прим применяет его к разрезу «уже построенное дерево против остальных вершин», Крускал — неявно, обрабатывая рёбра по возрастанию веса, применяет его ко всем возможным разрезам сразу через доказательство от противного (если бы минимальное ребро между двумя компонентами не входило в MST, замена любого другого пути между этими компонентами на это ребро могла бы только уменьшить суммарный вес). Понимание этого общего математического основания — то, что объясняет, почему совершенно разные по коду и логике алгоритмы всегда приходят к одному и тому же (при разных весах — буквально идентичному) результату.
Практический же выбор между двумя алгоритмами определяется структурой конкретного графа и тем, как эти данные физически представлены в программе.
Примеры с разбором
Пример 1. Плотный граф: когда выигрывает Прим с матрицей смежности. Рассмотрим граф с $V=1000$ вершинами, близкий к полному, то есть $E \approx V^2/2 \approx 500\,000$ рёбер. Алгоритм Крускала потребует сортировки полумиллиона рёбер — $O(E\log E) \approx 500\,000 \cdot \log_2(500\,000) \approx 500\,000 \cdot 19 \approx 9{,}5$ млн операций сравнения, плюс накладные расходы на хранение и обработку списка такого размера. Алгоритм Прима с простой реализацией на матрице смежности (без кучи, с линейным поиском минимального граничного ребра на каждом из $V$ шагов) даёт сложность $O(V^2) = 1\,000\,000$ операций — на порядок меньше и, что важно, без затрат памяти на явное хранение полумиллиона объектов-рёбер, поскольку веса читаются напрямую из матрицы. Для плотных графов Прим с матрицей смежности почти всегда выигрывает и по времени, и по памяти.
Пример 2. Разреженный граф: когда выигрывает Крускал. Рассмотрим граф дорожной сети с $V=100\,000$ перекрёстков, но всего $E=300\,000$ дорог (типичное соотношение для реальных дорожных сетей — каждый перекрёсток соединён лишь с несколькими соседними, а не со всеми остальными). Здесь $E$ значительно меньше $V^2$, и алгоритм Прима с матрицей смежности размером $100\,000 \times 100\,000$ потребовал бы порядка $10^{10}$ ячеек памяти — физически нереализуемо. Алгоритм Крускала со списком из $300\,000$ рёбер и структурой Union-Find обходится сортировкой $O(E\log E) \approx 300\,000 \cdot 19 \approx 5{,}7$ млн операций и практически линейной по $E$ работой Union-Find — на много порядков дешевле по памяти и вполне сопоставимо по времени. Для разреженных графов Крускал (или Прим с кучей и списком смежности, что даёт ту же асимптотику $O(E\log V)$) — практически обязательный выбор.
Пример 3. Применение: проектирование сети с минимальными затратами. Пусть телекоммуникационная компания должна связать оптоволоконным кабелем шесть населённых пунктов, расстояния между которыми (в километрах, отражающих реальную стоимость прокладки) в точности совпадают с весами графа из предыдущих разделов ($A,B,C,D,E,F$ с рёбрами, перечисленными выше). Прямое применение любого из двух алгоритмов даёт MST суммарной стоимостью $13$ условных единиц — это и есть минимально возможные затраты на связывание всех шести городов в единую сеть без единого лишнего, избыточного соединения. Если бы инженер вместо этого просто проложил кабель между каждой парой соседних по карте городов «на глаз», не считая MST, суммарные затраты почти наверняка оказались бы выше — причём для крупной реальной сети (сотни узлов) разница между «на глаз спроектированной» сетью и настоящим MST может составлять десятки процентов от бюджета проекта.
Почему это важно. Осознанный выбор алгоритма — не формальность, а вопрос реальных вычислительных ресурсов на графах промышленного масштаба: неверный выбор представления и алгоритма может превратить задачу, решаемую за секунды, в задачу, требующую терабайтов памяти или часов вычислений. Ровно так же, как выбор между красно-чёрным деревом и B-деревом в предыдущих уроках определялся физикой хранения данных, выбор между алгоритмом Прима и алгоритмом Крускала определяется плотностью графа и форматом, в котором данные физически доступны программе.
Применение: иерархическая кластеризация методом одиночной связи
Теперь — к связи с машинным обучением, обещанной во вступлении. В иерархической агломеративной кластеризации методом одиночной связи (single linkage) алгоритм стартует с того, что каждая точка данных — это отдельный кластер, а затем на каждом шаге объединяет два кластера, расстояние между которыми (определённое как расстояние между их ближайшей парой точек) минимально среди всех пар кластеров. Если представить точки данных как вершины полного графа, а попарные расстояния между ними — как веса рёбер, то процедура single linkage — это в точности алгоритм Крускала: рёбра (пары точек) обрабатываются в порядке возрастания расстояния, и каждое ребро, соединяющее два ещё не связанных кластера, включается в растущую структуру, точно повторяя проверку через Union-Find (принадлежат ли точки уже одному кластеру или разным).
Дендрограмма — стандартная визуализация иерархической кластеризации в виде дерева слияний — это, по сути, MST с дополнительной информацией о порядке (и «высоте», то есть весе) каждого слияния. Более того, зная минимальное остовное дерево набора точек, можно получить кластеризацию методом одиночной связи на любое желаемое число кластеров $k$ буквально за один дополнительный шаг: нужно взять $k-1$ самых тяжёлых рёбер MST и удалить их — оставшийся лес из $k$ компонент и есть искомые $k$ кластеров. Это делает MST не просто теоретической иллюстрацией к кластеризации, а прямым практическим инструментом её реализации — многие библиотеки, реализующие single linkage эффективно, буквально строят MST под капотом (часто через вариант алгоритма Прима, поскольку матрица попарных расстояний между точками — это плотный граф, для которого Прим с массивом асимптотически предпочтительнее).
Практика: 30 заданий
Базовые (задания 1–10)
Задание 1. Дан связный граф из $7$ вершин. Сколько рёбер содержит любое остовное дерево этого графа? Обоснуй ответ.
Задание 2. Дан граф-треугольник с вершинами $X, Y, Z$ и рёбрами $XY=6$, $YZ=9$, $XZ=4$. Найди минимальное остовное дерево вручную.
Задание 3. В графе с рёбрами $PQ=3$, $QR=3$, $PR=8$ (треугольник с двумя равными минимальными весами) — сколько существует различных минимальных остовных деревьев? Перечисли их.
Задание 4. По формуле Кэли посчитай число различных остовных деревьев полного графа $K_5$ (5 вершин, каждая пара соединена ребром).
Задание 5. Дан граф с вершинами $A,B,C$ и рёбрами $AB=7$, $AC=2$, $BC=5$. Запусти алгоритм Прима со стартом в $A$ и укажи, какое ребро будет добавлено первым.
Задание 6. Для графа с рёбрами $MN=6$, $NK=2$, $MK=9$, $KL=4$ отсортируй все рёбра по неубыванию веса — это первый шаг алгоритма Крускала.
Задание 7. В структуре Union-Find после нескольких операций union получилось: find(3) = 1, find(5) = 1, find(7) = 4. Находятся ли вершины $3$ и $5$ в одном множестве? А вершины $3$ и $7$?
Задание 8. При выполнении алгоритма Крускала уже добавлены рёбра, объединившие вершины в множества $\{1,2,4\}$ и $\{3,5\}$. Следующее по сортировке ребро — $(2,4)$. Будет ли оно добавлено? Обоснуй.
Задание 9. Дан граф из $4$ вершин с рёбрами $AB=1$, $BC=2$, $CD=3$, $DA=4$, $AC=10$. Найди MST и его суммарный вес.
Задание 10. Своими словами объясни разницу между «остовным деревом» и «минимальным остовным деревом» графа.
Средние (задания 11–20)
Задание 11. Дан граф с вершинами $P,Q,R,S,T$ и рёбрами $PQ=4$, $PR=1$, $QR=3$, $QS=2$, $RS=5$, $ST=6$, $RT=7$. Выполни полную трассировку алгоритма Прима со стартом в $P$.
Задание 12. Для того же графа, что в задании 11, выполни полную трассировку алгоритма Крускала и сравни итоговый результат.
Задание 13. В Union-Find без сжатия пути и без объединения по рангу выполнена цепочка операций union(1,2), union(2,3), union(3,4), union(4,5), каждый раз подвешивая корень второго аргумента под корень первого. Опиши, как выглядит структура parent, и оцени стоимость find(5).
Задание 14. Граф имеет $V=200$ вершин и является почти полным ($E\approx 19\,900$ рёбер). Какую реализацию алгоритма Прима выгоднее использовать — с матрицей смежности $O(V^2)$ или с бинарной кучей $O(E\log V)$? Приведи численную оценку.
Задание 15. Граф имеет $V=1000$ вершин и $E=5000$ рёбер (разреженный). Оцени порядок числа операций для алгоритма Крускала (доминирует сортировка) и сравни с $O(V^2)$ для Прима с матрицей.
Задание 16. Граф содержит рёбра с отрицательными весами (например, ребро веса $-3$). Останутся ли корректными алгоритмы Прима и Крускала? Сравни с ситуацией в алгоритме Дейкстры.
Задание 17. Дан граф с рёбрами $AB=2$, $BC=2$, $AC=5$, $CD=2$, $BD=2$ (несколько рёбер веса $2$). Найди хотя бы два различных MST.
Задание 18. Пять зданий на плане участка нужно соединить проводкой с минимальными затратами; попарные расстояния (в метрах) между зданиями $1..5$: $d(1,2)=10$, $d(1,3)=6$, $d(2,3)=5$, $d(2,4)=15$, $d(3,4)=4$, $d(3,5)=8$, $d(4,5)=6$. Найди MST и общую длину проводки.
Задание 19. Дан набор из четырёх точек данных с попарными расстояниями $d(1,2)=1$, $d(1,3)=4$, $d(1,4)=5$, $d(2,3)=3$, $d(2,4)=6$, $d(3,4)=2$. Построй MST и укажи порядок объединений — это и есть порядок слияний кластеров в методе одиночной связи.
Задание 20. Объясни, почему объединение по рангу (всегда подвешивать более низкое дерево под более высокое) не даёт высоте результирующего DSU-дерева расти быстрее $O(\log n)$.
Продвинутые (задания 21–30)
Задание 21. Сформулируй неформальное обоснование свойства разреза (cut property): почему минимальное ребро, пересекающее любой разрез графа на две непустые части, всегда безопасно включить в MST.
Задание 22. Сформулируй свойство цикла (cycle property): почему самое тяжёлое ребро любого цикла графа (при условии, что оно строго тяжелее остальных рёбер цикла) никогда не входит в MST.
Задание 23. Как модифицировать алгоритм Крускала, чтобы он находил не минимальное, а максимальное остовное дерево? Обоснуй корректность модификации.
Задание 24. Что произойдёт при запуске алгоритма Крускала на несвязном графе (состоящем из двух отдельных компонент)? Что вернёт алгоритм?
Задание 25. В чём главное практическое преимущество алгоритма Борувки перед алгоритмами Прима и Крускала на графах огромного размера, распределённых по многим вычислительным узлам?
Задание 26. Дано MST с $6$ вершинами и $5$ рёбрами весов $1, 2, 3, 5, 8$ (в порядке добавления методом одиночной связи). Как получить ровно $3$ кластера из этого дерева?
Задание 27. Дан граф с вершинами $1..7$ и рёбрами: $1$-$2$:2, $1$-$3$:4, $2$-$3$:1, $2$-$4$:7, $3$-$5$:3, $4$-$5$:2, $4$-$6$:5, $5$-$6$:4, $5$-$7$:6, $6$-$7$:1. Выполни полную трассировку алгоритма Крускала, явно показывая состояние Union-Find на каждом шаге.
Задание 28. При использовании фибоначчиевой кучи вместо бинарной алгоритм Прима достигает сложности $O(E + V\log V)$ вместо $O(E\log V)$. Для какого типа графов эта разница особенно заметна? Приведи численную оценку для $V=10^5$, $E=10^5$ (разреженный граф).
Задание 29. Спроектируй сеть проводки между $6$ городами с координатами (в условных единицах): $A(0,0)$, $B(2,0)$, $C(1,2)$, $D(4,1)$, $E(3,3)$, $F(5,3)$. Используя евклидово расстояние, найди MST и суммарную длину сети (расстояния можно округлить до одного знака после запятой).
Задание 30. Сравни три сценария и для каждого обоснуй выбор алгоритма построения MST: (а) плотный граф расстояний между $500$ точками на плоскости (матрица $500\times500$ уже посчитана); (б) разреженная сеть дорог с $2$ млн перекрёстков и $5$ млн дорог, заданная списком рёбер; (в) огромный граф социальных связей с миллиардами вершин, распределённый по кластеру из сотен серверов.
Частые ошибки
❌ Ошибка: Считать, что минимальное остовное дерево всегда содержит кратчайшие пути между всеми парами вершин исходного графа.
✅ Правильно: MST минимизирует только суммарный вес всех выбранных рёбер вместе, а не расстояние между какой-то конкретной парой вершин — путь между двумя вершинами внутри MST может оказаться значительно длиннее, чем кратчайший путь между ними в исходном графе.
💡 Почему: Это две принципиально разные оптимизационные задачи (как показано в сравнении с алгоритмом Флойда-Уоршелла в начале урока): MST оптимизирует связность всей сети целиком, а не путь между двумя точками.
❌ Ошибка: В алгоритме Прима сравнивать на каждом шаге все рёбра графа, а не только рёбра, ведущие от уже построенного дерева наружу.
✅ Правильно: На каждом шаге рассматриваются только рёбра, у которых ровно один конец находится внутри уже построенного дерева, а второй — снаружи.
💡 Почему: Ребро, оба конца которого уже внутри дерева, неизбежно создаст цикл при добавлении — такие рёбра в принципе не могут быть кандидатами.
❌ Ошибка: В алгоритме Крускала забыть проверять, не создаёт ли рассматриваемое ребро цикл, и добавлять просто первые $n-1$ рёбер по возрастанию веса.
✅ Правильно: Каждое ребро проверяется через Union-Find — добавляется, только если его концы принадлежат разным множествам; иначе оно пропускается, даже если общее число уже добавленных рёбер меньше $n-1$.
💡 Почему: Без проверки цикла набор из первых $n-1$ рёбер по весу может оказаться несвязным или содержать циклы — он попросту не будет деревом.
❌ Ошибка: Реализовывать проверку «находятся ли две вершины в одной компоненте» через обход графа (DFS/BFS) на каждом шаге алгоритма Крускала вместо структуры Union-Find.
✅ Правильно: Использовать специализированную структуру Union-Find с объединением по рангу и сжатием пути — проверка и объединение обходятся почти за константное время.
💡 Почему: Обход графа на каждом из $E$ шагов стоит $O(V+E)$ каждый раз, что даёт итоговую сложность $O(E(V+E))$ — на порядки хуже, чем $O(E\log E)$ с полноценным Union-Find, и делает алгоритм непрактичным уже на графах средней величины.
❌ Ошибка: Полагать, что при равных весах рёбер алгоритмы Прима и Крускала обязательно построят один и тот же набор рёбер.
✅ Правильно: Гарантия одинакового результата справедлива только при попарно различных весах рёбер; при наличии равных весов оба алгоритма гарантированно находят дерево с одинаковой минимальной суммой веса, но конкретный набор выбранных рёбер может различаться.
💡 Почему: При равных весах порядок обработки «равноправных» кандидатов зависит от реализации (порядок обхода списка смежности в Приме, порядок рёбер с одинаковым весом после сортировки в Крускале) и может привести к разным, но одинаково оптимальным по суммарному весу деревьям.
❌ Ошибка: Пытаться применить алгоритм Прима или Крускала напрямую к несвязному графу, ожидая единое дерево на выходе.
✅ Правильно: Для несвязного графа минимального остовного дерева не существует в принципе — оба алгоритма в лучшем случае построят минимальный остовный лес (по одному дереву на каждую компоненту связности), и это нужно явно предусмотреть в реализации (проверять число добавленных рёбер, а не полагаться на автоматическую остановку).
💡 Почему: Если не проверять связность заранее или число добавленных рёбер по ходу работы, программа может незаметно вернуть неполный, ошибочный результат, приняв его за корректное MST.
Главное запомнить
✅ Остовное дерево — связный подграф без циклов, охватывающий все $n$ вершин графа и содержащий ровно $n-1$ ребро; минимальное остовное дерево (MST) — то из остовных деревьев, у которого суммарный вес рёбер минимален
✅ MST может быть неединственным, если в графе есть рёбра с равным весом; единственность гарантирована только при попарно различных весах
✅ Алгоритм Прима жадно растит единое связное дерево от одной стартовой вершины, на каждом шаге добавляя минимальное ребро, ведущее от уже построенного дерева к новой вершине; сложность $O(E\log V)$ с бинарной кучей или $O(V^2)$ с матрицей смежности
✅ Алгоритм Крускала сортирует все рёбра графа по весу и жадно добавляет каждое следующее, если оно не создаёт цикл с уже добавленными рёбрами; сложность $O(E\log E)$, доминирует сортировка
✅ Union-Find (система непересекающихся множеств) с объединением по рангу и сжатием пути позволяет проверять принадлежность двух вершин одной компоненте и объединять компоненты почти за константное время — амортизированная сложность $O(\alpha(n))$
✅ Корректность обоих алгоритмов доказывается свойством разреза (минимальное ребро, пересекающее любой разрез графа, безопасно включить в MST) и симметричным ему свойством цикла (самое тяжёлое ребро любого цикла безопасно исключить из MST)
✅ Прим с матрицей смежности предпочтителен на плотных графах ($E$ близко к $V^2$); Крускал (или Прим с кучей) предпочтителен на разреженных графах, особенно если данные уже заданы списком рёбер
✅ MST не решает задачу кратчайшего пути между конкретной парой вершин — это две разные оптимизационные задачи на графах, и путать их нельзя
✅ MST лежит в основе проектирования сетей с минимальными затратами (кабели, дороги, электросети) и является прямым алгоритмическим фундаментом иерархической кластеризации методом одиночной связи — дендрограмма кластеризации совпадает с порядком добавления рёбер в MST
✅ Алгоритм Борувки (1926) — исторически первый алгоритм построения MST, естественно параллелизуемый и вновь актуальный для распределённых вычислений на графах огромного размера
Связь с другими темами курса
🔙 Откуда пришли: Из урока 264 — алгоритм Флойда-Уоршелла решал задачу кратчайших путей между всеми парами вершин; MST ставит принципиально другую задачу на том же типе данных (взвешенный граф) — не оптимальный путь между парой точек, а оптимальную структуру связности всей сети сразу.
🔜 Куда идём:
- Алгоритмы сортировки (урок 266) — алгоритм Крускала целиком опирается на эффективную сортировку рёбер по весу, и следующий блок курса разберёт, как устроены сами алгоритмы сортировки изнутри
- Жадные алгоритмы как отдельный класс стратегий — и Прим, и Крускал служат каноническими примерами того, когда локально оптимальный выбор на каждом шаге гарантированно приводит к глобально оптимальному решению, в отличие от многих других задач, где жадная стратегия даёт лишь приближённый результат
🎯 В машинном обучении: Минимальное остовное дерево — прямой алгоритмический фундамент иерархической кластеризации методом одиночной связи (single linkage): последовательность объединений кластеров в этом методе в точности повторяет порядок добавления рёбер в MST алгоритмом Крускала, а дендрограмма — это визуализация MST с сохранённым порядком слияний. Получить кластеризацию на любое число кластеров $k$ из готового MST можно за один шаг — удалением $k-1$ самых тяжёлых рёбер. За пределами кластеризации MST используется для анализа связности графов признаков (например, для построения приближённых структур графового представления данных перед подачей в модели, работающие на графах) и как компонент приближённых эвристик для задачи коммивояжёра, где MST даёт доказуемую нижнюю границу стоимости оптимального маршрута.
Интересные факты
📌 Алгоритм Борувки 1926 года решал не абстрактную математическую задачу, а совершенно конкретную инженерную: минимизацию затрат на электрификацию Моравии — региона, где в 1920-х годах массово прокладывались первые линии электропередачи, и каждый лишний километр провода стоил реальных денег в бюджете, ограниченном возможностями молодой Чехословацкой Республики.
📌 Алгоритм, который сегодня называют алгоритмом Прима, был впервые опубликован чешским математиком Войтехом Ярником ещё в 1930 году — на 27 лет раньше публикации Роберта Прима в 1957 году. Из-за языкового барьера (публикация на чешском языке) работа Ярника десятилетиями оставалась практически неизвестной за пределами Чехословакии, и в большинстве источников алгоритм по сей день называется просто «алгоритмом Прима», хотя более полное и исторически точное название — «алгоритм Ярника — Прима».
📌 Формула Кэли ($n^{n-2}$ остовных деревьев для полного графа на $n$ вершинах) была доказана Артуром Кэли в 1889 году, но самое элегантное её доказательство — через так называемый код Прюфера, биекцию между остовными деревьями и последовательностями чисел длины $n-2$ — появилось только полвека спустя, в 1918 году, и остаётся стандартным способом доказательства этой формулы в современных учебниках комбинаторики.
📌 Задача коммивояжёра (нахождение кратчайшего маршрута, посещающего все города ровно один раз) NP-трудна и не имеет известного эффективного точного решения, но простая эвристика на основе MST (удвоение рёбер минимального остовного дерева и построение эйлерова обхода) гарантированно даёт маршрут не длиннее чем в два раза дороже оптимального — редкий случай, когда задача о MST, решаемая за полиномиальное время, служит доказуемой опорой для приближённого решения куда более сложной задачи.
Лайфхаки и полезные трюки
💡 Если не помнишь, какой алгоритм эффективнее на конкретном графе, задай себе один вопрос: граф плотный ($E$ близко к $V^2$) или разреженный ($E$ намного меньше $V^2$)? Плотный — выбирай Прима с матрицей смежности; разреженный, особенно уже заданный списком рёбер, — выбирай Крускала.
💡 При отладке реализации любого из алгоритмов всегда проверяй два инварианта: во-первых, число рёбер в результате должно быть ровно $n-1$ (для связного графа), во-вторых, суммарный вес не должен зависеть от стартовой вершины (для Прима) или от порядка рёбер с одинаковым весом (для Крускала) — если эти проверки не сходятся, ищи ошибку в логике сравнения весов или в обработке уже посещённых вершин.
💡 Реализуя Union-Find, не экономь на обеих оптимизациях сразу — объединение по рангу и сжатие пути обычно занимают по три-четыре строки кода каждая, но вместе дают амортизированную сложность, практически неотличимую от константы; реализация без обеих оптимизаций может незаметно деградировать до $O(n)$ на одной операции и испортить асимптотику всего алгоритма Крускала.
💡 Если требуется не просто MST, а кластеризация на конкретное число групп $k$, не запускай отдельный алгоритм кластеризации с нуля — построй MST один раз (через Крускала, с сохранением списка добавленных рёбер в порядке возрастания веса) и просто отбрось $k-1$ самых тяжёлых из уже добавленных рёбер: это даёт результат метода одиночной связи практически бесплатно, без повторного прохода по всем попарным расстояниям.
💡 На собеседованиях по алгоритмам вопрос про MST почти всегда сопровождается просьбой доказать корректность жадного выбора — готовься объяснять именно свойство разреза (cut property) своими словами и на конкретном примере, а не просто пересказывать псевдокод: понимание «почему жадность здесь работает» ценится выше, чем умение написать код по памяти.
💡 Если граф очень большой и не помещается на одной машине, не пытайся напрямую адаптировать Прима или Крускала под распределённую среду — вместо этого посмотри в сторону алгоритма Борувки или его современных потомков (используемых, например, в библиотеках распределённой обработки графов): раундовая, независимая по фрагментам структура этого алгоритма спроектирована для параллелизма значительно лучше, чем последовательный рост дерева или централизованная сортировка.
Минимальное остовное дерево — это ровно тот случай, когда красивая математическая гарантия (свойство разреза, делающее жадный выбор безопасным на каждом шаге) напрямую превращается в инструмент, который экономит реальные деньги на прокладке реальных сетей и лежит внутри одного из самых распространённых методов кластеризации в машинном обучении. Ты увидел два совершенно разных по устройству, но одинаково корректных жадных алгоритма — растущий от одной точки Прим и сортирующий все рёбра сразу Крускал, — и разобрался, почему выбор между ними определяется не личным вкусом, а плотностью графа и форматом, в котором физически доступны данные. Дальше в курсе эта идея жадных алгоритмов на графах получит развитие в алгоритмах сортировки — том самом строительном блоке, без которого алгоритм Крускала не смог бы упорядочить рёбра графа за разумное время.
Понял тему? Закрепи в боте! 🚀
Попрактикуйся на задачах и получи персональные рекомендации от AI
💪 Начать тренировку