15.2 Алгоритм Краскала¶

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

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

• все вершины оказались связаны;
• циклов не было;
• суммарный вес выбранных рёбер был минимален.

Такой набор рёбер называется минимальным остовным деревом.

Если в графе n вершин, то в любом остовном дереве будет ровно n-1 ребро. Это очень важный факт: как только мы набрали n-1 ребро и граф стал связным, ответ готов.

Алгоритм Краскала — один из самых популярных способов построить минимальное остовное дерево.

Идея алгоритма¶

Интуиция очень простая:

1. Рассмотрим все рёбра графа.
2. Отсортируем их по весу по возрастанию.
3. Будем идти по ним слева направо.
4. Если текущее ребро соединяет две разные компоненты связности, то добавим его.
5. Если оно соединяет вершины, которые уже и так связаны, то пропустим его, потому что оно создаст цикл.

То есть алгоритм всегда старается взять самое дешёвое из безопасных рёбер.

Почему нельзя просто брать самые маленькие рёбра подряд¶

Если брать только самые лёгкие рёбра без проверки, легко получить цикл.

Например, если есть треугольник с рёбрами весов 1, 2 и 3, то нельзя взять все три ребра, потому что это уже не дерево.

Поэтому у Краскала есть ключевое правило:

добавляем ребро только тогда, когда оно соединяет разные компоненты.

Именно это сохраняет структуру дерева.

Пошаговый пример¶

Рассмотрим граф с вершинами 1..6 и рёбрами:

• 5-6 вес 2
• 1-2 вес 3
• 3-6 вес 3
• 1-5 вес 5
• 2-3 вес 5
• 2-5 вес 6
• 4-6 вес 7
• 3-4 вес 9

После сортировки список уже выглядит так же:

Теперь идём по списку.

Шаг 1¶

Берём 5-6.

Компоненты были {5} и {6}, стали {5,6}.

Шаг 2¶

Берём 1-2.

Компоненты {1} и {2} объединяются в {1,2}.

Шаг 3¶

Берём 3-6.

Компоненты {3} и {5,6} объединяются в {3,5,6}.

Шаг 4¶

Берём 1-5.

Компоненты {1,2} и {3,5,6} объединяются в {1,2,3,5,6}.

Шаг 5¶

Рассматриваем 2-3.

Но вершины 2 и 3 уже находятся в одной компоненте. Если добавить это ребро, получится цикл. Пропускаем.

Шаг 6¶

Рассматриваем 2-5.

Ситуация та же: обе вершины уже в одной компоненте. Пропускаем.

Шаг 7¶

Берём 4-6.

Компоненты {4} и {1,2,3,5,6} объединяются.

Теперь все вершины соединены. Получили остовное дерево.

Выбранные рёбра:

• 5-6 вес 2
• 1-2 вес 3
• 3-6 вес 3
• 1-5 вес 5
• 4-6 вес 7

Суммарный вес:

2 + 3 + 3 + 5 + 7 = 20

Наглядная схема процесса¶

graph LR
    A[Старт: каждая вершина отдельно] --> B[Отсортировать рёбра по весу]
    B --> C{Ребро соединяет
разные компоненты?}
    C -->|Да| D[Добавить ребро]
    C -->|Нет| E[Пропустить ребро]
    D --> F{Уже выбрано n-1 рёбер?}
    E --> F
    F -->|Нет| C
    F -->|Да| G[Минимальное остовное дерево готово]

Почему алгоритм Краскала корректен¶

Главная идея доказательства такая:

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

Почему?

Представим, что мы не взяли такое ребро e, хотя оно соединяло две разные части графа. Но в любом остовном дереве эти части всё равно должны как-то соединяться. Значит, там есть какое-то другое ребро f, которое тоже соединяет эти две части.

Так как e — самое дешёвое подходящее ребро на этом шаге, то

weight(e) <= weight(f)

Если заменить f на e, дерево не станет тяжелее. Значит, существует оптимальное решение, в котором e присутствует.

Это и означает, что жадный выбор не портит ответ.

Дальше тот же аргумент повторяется шаг за шагом.

Как понять алгоритм на интуитивном уровне¶

Краскал как будто строит лес:

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

То есть алгоритм не думает о всём графе сразу. Он просто аккуратно объединяет куски, никогда не делая лишних дорогих соединений.

Что нужно уметь для реализации¶

Чтобы алгоритм работал быстро, нам нужно уметь отвечать на два вопроса:

1. Находятся ли вершины a и b в одной компоненте?
2. Если нет, как быстро объединить их компоненты?

Для этого почти всегда используют структуру DSU / Union-Find.

Она поддерживает операции:

• find(v) — найти представителя компоненты вершины v;
• unite(a, b) — объединить компоненты вершин a и b.

Благодаря DSU алгоритм Краскала работает очень быстро.

Стандартная реализация на C++¶

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;

    DSU(int n) {
        p.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) p[i] = i;
    }

    int find(int v) {
        if (p[v] == v) return v;
        return p[v] = find(p[v]);
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Edge {
    int u, v, w;

    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges.begin(), edges.end());

    DSU dsu(n);
    long long ans = 0;
    vector<Edge> mst;

    for (auto e : edges) {
        if (dsu.unite(e.u, e.v)) {
            ans += e.w;
            mst.push_back(e);
        }
    }

    if ((int)mst.size() != n - 1) {
        cout << "NO MST\n";
        return 0;
    }

    cout << ans << "\n";
    for (auto e : mst) {
        cout << e.u << " " << e.v << " " << e.w << "\n";
    }

    return 0;
}

Как работает этот код¶

1. Считываем рёбра¶

Каждое ребро хранит:

• одну вершину u;
• другую вершину v;
• вес w.

2. Сортируем рёбра¶

После sort(edges.begin(), edges.end()) рёбра идут от самых дешёвых к самым дорогим.

3. Идём по рёбрам¶

Для каждого ребра проверяем:

• если концы в разных компонентах — объединяем и добавляем вес в ответ;
• если в одной — пропускаем.

4. Проверяем, получился ли остов¶

Если граф был связным, то мы должны выбрать ровно n-1 ребро.

Если выбрали меньше, значит граф был несвязным и остовного дерева для всех вершин не существует. В таком случае говорят уже не о дереве, а о минимальном остовном лесе.

Другая версия¶

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int a, b, w;
};

bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}

vector<int> p, sz;

int find_set(int v) {
    if (p[v] == v) return v;
    p[v] = find_set(p[v]);
    return p[v];
}

bool unite_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Edge> e(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i].a >> e[i].b >> e[i].w;
    }

    sort(e.begin(), e.end(), cmp);

    p.resize(n + 1);
    sz.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) p[i] = i;

    long long ans = 0;
    int cnt = 0;

    for (int i = 0; i < m; i++) {
        if (unite_set(e[i].a, e[i].b)) {
            ans += e[i].w;
            cnt++;
        }
    }

    if (cnt != n - 1) {
        cout << "NO MST\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

Оценка сложности¶

Пусть в графе:

• n — число вершин,
• m — число рёбер.

Тогда:

• сортировка рёбер занимает O(m log m);
• операции DSU работают очень быстро и суммарно почти линейны.

Поэтому общая сложность обычно записывается как:

O(m log m)

Так как в простом графе m <= n^2, иногда пишут и O(m log n), но стандартнее запоминать именно O(m log m) из-за сортировки.

Когда Краскал особенно удобен¶

Алгоритм Краскала очень хорош, когда:

• граф задан списком рёбер;
• нужно просто построить MST;
• граф разреженный или средней плотности;
• под рукой уже есть DSU.

Во многих задачах олимпиадного программирования Краскал — первый кандидат на применение.

Типичные ошибки¶

1. Забыли сортировку¶

Если рёбра не отсортированы, алгоритм перестаёт быть алгоритмом Краскала и ответ может стать неверным.

2. Добавляют ребро без проверки компоненты¶

Тогда может появиться цикл.

3. Не проверяют связность графа¶

Если граф изначально несвязный, MST для всех вершин не существует.

4. Хранят сумму в int¶

Если рёбер много и веса большие, сумма может не поместиться. Лучше использовать long long.

5. Ошибка в индексации¶

Нужно внимательно следить, вершины нумеруются с 0 или с 1.

Маленький тренировочный пример¶

Вход:

4 5
1 2 4
1 3 3
2 3 2
2 4 5
3 4 7

Разберём вручную.

После сортировки:

• 2-3 (2)
• 1-3 (3)
• 1-2 (4)
• 2-4 (5)
• 3-4 (7)

Берём:

• 2-3
• 1-3
• 2-4

Ребро 1-2 пропускаем, потому что оно образует цикл внутри уже собранной компоненты {1,2,3}.

Ответ:

2 + 3 + 5 = 10

Краткое сравнение с алгоритмом Прима (рассмторим в 15.3)¶

И Краскал, и Прим строят минимальное остовное дерево, но делают это по-разному:

• Краскал сортирует все рёбра и объединяет компоненты.
• Прим наращивает одно дерево, каждый раз добавляя ближайшую новую вершину.

На практике оба алгоритма полезны. Но в олимпиадных задачах Краскал особенно любят за простоту вместе с DSU.

Что важно запомнить¶

• Минимальное остовное дерево соединяет все вершины с минимальной суммой весов.
• Алгоритм Краскала рассматривает рёбра по возрастанию веса.
• Ребро добавляется только если соединяет разные компоненты.
• Для быстрой реализации используется DSU / Union-Find.
• Основная сложность — O(m log m).