Минимальное остовное дерево: алгоритмы Прима и Краскала на Python

Коротко

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

Что такое остовное дерево

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

• соединяет все вершины;
• не содержит циклов;
• состоит ровно из V−1 рёбер, где V — число вершин.

Минимальное остовное дерево (MST) — то, у которого суммарный вес рёбер наименьший.

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

Ключевая идея, общая для обоих алгоритмов

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

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

Отсюда обе стратегии: Прим наращивает одно дерево, Краскал склеивает много мелких.

Алгоритм Прима: растим дерево из одной точки

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

Аналогия — растущая клякса. Она расползается всегда в ту сторону, где дешевле.

import heapq


def prim(graph: dict[int, list[tuple[int, int]]], start: int = 0):
    """graph: вершина -> список (сосед, вес). Возвращает (вес, рёбра)."""
    visited = {start}
    edges = []
    total = 0

    # куча кандидатов: (вес, откуда, куда)
    heap = [(w, start, to) for to, w in graph[start]]
    heapq.heapify(heap)

    while heap and len(visited) < len(graph):
        weight, frm, to = heapq.heappop(heap)

        if to in visited:
            continue  # ребро внутрь дерева — создаст цикл

        visited.add(to)
        edges.append((frm, to, weight))
        total += weight

        for nxt, w in graph[to]:
            if nxt not in visited:
                heapq.heappush(heap, (w, to, nxt))

    return total, edges


graph = {
    0: [(1, 4), (2, 1)],
    1: [(0, 4), (2, 2), (3, 5)],
    2: [(0, 1), (1, 2), (3, 8)],
    3: [(1, 5), (2, 8)],
}

print(prim(graph))
# (8, [(0, 2, 1), (2, 1, 2), (1, 3, 5)])

Проверка if to in visited: continue обязательна. В кучу могут попасть рёбра, ведущие в вершины, которые к моменту извлечения уже добавлены, — их нужно молча пропускать.

Алгоритм Краскала: склеиваем компоненты

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

Аналогия — несколько отдельных островков, которые постепенно срастаются мостами, начиная с самых дешёвых.

Главный вопрос: как быстро проверять, лежат ли две вершины в одной компоненте? Для этого используется система непересекающихся множеств (DSU).

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        # сжатие путей: подвешиваем всё напрямую к корню
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # уже в одной компоненте

        # объединение по рангу: меньшее дерево вешаем к большему
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


def kruskal(n: int, edges: list[tuple[int, int, int]]):
    """edges: список (вес, u, v)."""
    dsu = DSU(n)
    result = []
    total = 0

    for weight, u, v in sorted(edges):
        if dsu.union(u, v):
            result.append((u, v, weight))
            total += weight
            if len(result) == n - 1:
                break  # дерево собрано

    return total, result


edges = [(4, 0, 1), (1, 0, 2), (2, 1, 2), (5, 1, 3), (8, 2, 3)]
print(kruskal(4, edges))
# (8, [(0, 2, 1), (1, 2, 2), (1, 3, 5)])

Оба алгоритма дали вес 8 — как и должно быть.

Досрочный выход при len(result) == n - 1 экономит время: как только набрали нужное число рёбер, остальные можно не смотреть.

Разбор Краскала по шагам

На графе из примера рёбра после сортировки: (1: 0–2), (2: 1–2), (4: 0–1), (5: 1–3), (8: 2–3).

ребро 0–2 (вес 1):  компоненты {0,2} {1} {3}      → берём
ребро 1–2 (вес 2):  компоненты {0,1,2} {3}        → берём
ребро 0–1 (вес 4):  0 и 1 уже вместе              → пропускаем (цикл)
ребро 1–3 (вес 5):  компоненты {0,1,2,3}          → берём
                    набрали 3 = V−1 рёбер, стоп

итого: 1 + 2 + 5 = 8

Какой выбрать

Практическое правило: если рёбер много (E ≈ V²) — Прим; если мало (E ≈ V) — Краскал. На типичных задачах разница невелика, и Краскал обычно проще написать, если DSU уже есть под рукой.

Отдельный плюс Краскала: на несвязном графе он корректно построит минимальный остовный лес, тогда как Прим найдёт дерево только для компоненты, в которой стартовал.

Частые ошибки

Забытая проверка на цикл. Без неё оба алгоритма построят не дерево, а произвольный подграф с лишними рёбрами.

DSU без сжатия путей и рангов. Работать будет, но find деградирует до O(n), и Краскал станет квадратичным. Обе оптимизации — по три строки каждая.

Попытка применить MST там, где нужен кратчайший путь. Это разные задачи. Минимальное остовное дерево минимизирует суммарный вес всех рёбер, а не расстояние между конкретной парой вершин. Путь между двумя вершинами в MST может оказаться заметно длиннее кратчайшего. Для кратчайших путей нужен Дейкстра.

Ориентированный граф. Оба алгоритма работают только с неориентированными. Для ориентированных задача называется «минимальное остовное дерево с корнем» и решается алгоритмом Эдмондса, который заметно сложнее.

Что запомнить

• Остовное дерево соединяет все вершины V−1 ребром без циклов, минимальное — с наименьшим суммарным весом.
• Оба алгоритма жадные и опираются на свойство лёгкого ребра через разрез.
• Прим наращивает одно дерево через приоритетную очередь, Краскал склеивает компоненты через DSU.
• Прим выгоднее на плотных графах, Краскал — на разреженных.
• MST это не кратчайшие пути: путь между двумя вершинами в дереве может быть неоптимальным.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→