Algoritmi → Grafovi i stabla → Minimalno razapinjuće stablo: Kruskalov algoritam

Minimalno razapinjuće stablo: Kruskalov algoritam

Ideja

Treba povezati sve gradove putevima tako da se iz svakog može stići u svaki, a ukupna cena puteva bude najmanja. Izabrane grane tada čine stablo (ciklus bi značio jedan suvišan put) koje pokriva sve čvorove – minimalno razapinjuće stablo (MST, engl. minimum spanning tree). Ima tačno n − 1 granu.

        4
   1 ------- 2
   |  \      |
 1 |   \ 7   | 2
   |    \    |
   3 ------- 4 ---- 5
        5       3

Grane: 1–2 (4), 1–3 (1), 1–4 (7), 2–4 (2), 3–4 (5), 4–5 (3).

Zašto DSU?

DSU čuva podelu čvorova na grupe (komponente). Operacija nadji(v) vraća predstavnika grupe čvora v, a spoji(a, b) spaja dve grupe. Grana u–v pravi ciklus tačno kada su u i v već u istoj grupi. Uz kompresiju putanje i spajanje po veličini obe operacije su praktično O(1).

Program

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Grana { int w, u, v; };       // težina prva, da sortiranje ide po težini

vector<int> rod, vel;

int nadji(int v) {                   // predstavnik grupe, uz kompresiju putanje
    if (rod[v] == v) return v;
    return rod[v] = nadji(rod[v]);
}

bool spoji(int a, int b) {           // vraća false ako su već u istoj grupi
    a = nadji(a);
    b = nadji(b);
    if (a == b) return false;
    if (vel[a] < vel[b]) swap(a, b); // manju grupu kačimo na veću
    rod[b] = a;
    vel[a] += vel[b];
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Grana> g(m);
    for (auto &e : g) cin >> e.u >> e.v >> e.w;
    sort(g.begin(), g.end(), [](const Grana &a, const Grana &b) { return a.w < b.w; });
    rod.resize(n + 1);
    iota(rod.begin(), rod.end(), 0);   // rod[v] = v
    vel.assign(n + 1, 1);
    long long ukupno = 0;
    vector<Grana> izabrane;
    for (auto &e : g)
        if (spoji(e.u, e.v)) {         // krajevi su bili u različitim grupama
            ukupno += e.w;
            izabrane.push_back(e);
        }
    if ((int)izabrane.size() != n - 1) {
        cout << "graf nije povezan" << endl;
        return 0;
    }
    cout << ukupno << endl;
    for (auto &e : izabrane) cout << e.u << " " << e.v << " " << e.w << endl;
    return 0;
}

Složenost određuje sortiranje: O(m log m).

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje