Минимальное остовное дерево (MST)Minimum spanning tree (MST)

Остовное дерево (spanning tree) связного неориентированного графа — это подмножество его рёбер, которое связывает все V вершин, не образуя ни одного цикла. У любого связного графа с V вершинами остовное дерево всегда содержит ровно V-1 ребро (не больше — иначе появится цикл; не меньше — иначе граф распадётся на несколько частей). Минимальное остовное дерево — то из всех возможных остовных деревьев, у которого сумма весов рёбер наименьшая.A connected undirected graph's spanning tree is a subset of its edges connecting all V vertices with no cycle formed. Any connected graph with V vertices has a spanning tree with exactly V-1 edges (no more — that would create a cycle; no fewer — the graph would split into several pieces). The minimum spanning tree is, among all possible spanning trees, the one with the smallest total edge weight.

Стратегия: отсортировать все рёбра по весу по возрастанию, затем идти по ним и добавлять в MST каждое ребро, которое не создаёт цикл с уже добавленными — то есть соединяет две ещё не связанные между собой части. "Не создаёт цикл" проверяется структурой данных Disjoint Set Union (DSU, он же Union-Find): каждая компонента — это множество с одним представителем; `find(v)` находит представителя компоненты v, `union(u, v)` сливает две компоненты. Ребро добавляется в MST, только если `find(u) != find(v)` — иначе обе вершины уже в одной компоненте, и ребро создало бы цикл.The strategy: sort all edges by weight ascending, then walk through them and add to the MST every edge that doesn't create a cycle with what's already added — meaning it connects two parts not yet linked to each other. "Doesn't create a cycle" is checked with the Disjoint Set Union (DSU, aka Union-Find) data structure: each component is a set with one representative; `find(v)` finds v's component representative; `union(u, v)` merges two components. An edge is added to the MST only if `find(u) != find(v)` — otherwise both vertices are already in the same component, and the edge would create a cycle.

struct DSU {
    std::vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) { std::iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } // сжатие пути// path compression
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;                 // уже связаны — было бы циклом// already connected — would cycle
        if (rank_[a] < rank_[b]) std::swap(a, b);   // union by rank// union by rank
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

long long kruskal(int n, std::vector<std::array<int,3>> edges) { // {weight, u, v}// {weight, u, v}
    std::sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0;
    for (auto& [w, u, v] : edges)
        if (dsu.unite(u, v)) total += w;   // добавлено в MST// added to the MST
    return total;
}

Сжатие пути (path compression) в `find` и объединение по рангу (union by rank) в `unite` вместе дают почти константную амортизированную сложность операций — O(α(V)), где α — обратная функция Аккермана, растущая настолько медленно, что для любого практического V она не превышает 4-5. Сложность Крускала в целом определяется сортировкой рёбер — O(E log E).Path compression in `find` combined with union by rank in `unite` together give near-constant amortized complexity per operation — O(α(V)), where α is the inverse Ackermann function, growing so slowly that for any practical V it never exceeds 4-5. Kruskal's overall complexity is dominated by sorting the edges — O(E log E).

Прим растит MST из одной стартовой вершины, как Дейкстра растит дерево кратчайших путей: поддерживает множество уже включённых в MST вершин и на каждом шаге добавляет минимальное по весу ребро, ведущее из этого множества наружу (используя приоритетную очередь — почти буквально код Дейкстры с заменой "расстояние от старта" на "вес ребра до множества"). Оправдан на плотных графах, где Крускалу пришлось бы сортировать огромное количество рёбер.Prim's algorithm grows the MST from one starting vertex, the way Dijkstra grows a shortest-path tree: it maintains the set of vertices already in the MST, and at each step adds the minimum-weight edge leading from that set outward (using a priority queue — almost literally Dijkstra's code with "distance from source" replaced by "edge weight into the set"). It's justified on dense graphs, where Kruskal would have to sort an enormous number of edges.

Борувка — исторически первый алгоритм MST (1926 год) и единственный из трёх, естественно параллелизуемый: на каждом раунде КАЖДАЯ компонента одновременно находит своё минимальное исходящее ребро и добавляет его — число компонент минимум вдвое уменьшается за раунд, значит всего нужно O(log V) раундов. Именно эта параллелизуемость делает Борувку основой современных распределённых реализаций MST на графах, не помещающихся в память одной машины.Borůvka's algorithm is historically the first MST algorithm (1926) and the only one of the three that's naturally parallelizable: in each round, EVERY component simultaneously finds its minimum outgoing edge and adds it — the number of components at least halves per round, so only O(log V) rounds are needed total. This parallelizability is exactly why Borůvka's algorithm underlies modern distributed MST implementations on graphs too large to fit in one machine's memory.