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

Сначала сортируем список рёбер по неубыванию весов.

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

// Система непересекающихся множеств для быстрого определения, лежат ли концы ребра в разных компонентах связности

struct DSU {
    vector<int> parent;
    
    DSU(int n) {
        for (int v = 0; v < n; v++)
            parent.push_back(v);
    }
    
    int findRoot(int v) {
        return parent[v] == v ? v : parent[v] = findRoot(parent[v]);
    }
    
    bool connected(int v1, int v2) {
        return findRoot(v1) == findRoot(v2);
    }
    
    void merge(int v1, int v2) {
        int r1 = findRoot(v1), r2 = findRoot(v2);
        if (r1 == r2)
            return;
        if (rand() % 2)
            parent[r1] = r2;
        else
            parent[r2] = r1;
    }
};

// Структура для хранения взвешенного ребра
// Рёбра сравниваются по весу, список рёбер будет сортироваться по неубыванию весов

struct Edge {
    int a, b, weight;
    
    bool operator < (const Edge &that) const {
        return weight < that.weight;
    }
};

// Считывание списка рёбер графа
// (вершины во вводе нумеруются с 1, во внутреннем представлении — с 0)

int vertexCount, edgeCount;
cin >> vertexCount >> edgeCount;

vector<Edge> edges;
for (auto &[a, b, weight] : edges) {
    cin >> a >> b >> weight;
    a--;
    b--;
}

// Алгоритм Краскала
// (в данном примере определяется вес минимального остовного дерева — mstWeight)

int mstWeight = 0;

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

DSU dsu(vertexCount);
for (auto &[a, b, weight] : edges) {
    if (!dsu.connected(a, b)) {
        dsu.merge(a, b);
        mstWeight += weight;
    }
}

Сложность алгоритма Краскала:

• 1 раз выполняется сортировка списка рёбер за время O(ElogE);
• E раз выполняется запрос к системе непересекающихся множеств за O(1).

Итого сложность O(ElogE) = O(ElogV).

Для разреженных графов алгоритмы Прима и Краскала одинаково эффективны. Для плотных графов соответствующий вариант алгоритма Прима эффективнее, чем алгоритм Краскала.

Ссылки

Теория:

• e-maxx.ru — Алгоритм Крускала с системой непересекающихся множеств
• neerc.ifmo.ru/wiki — Алгоритм Краскала
• brestprog.by — Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала
• algorithmica.org — Минимальные остовы
• usaco.guide — MST
• algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees

Демонстрация:

• VisuAlgo — Minimum Spanning Tree

Код:

• algos/Graphs/MSTKruskal.cpp
• algs4/KruskalMST.java