MST — Kruskalov algoritam

Kruskalov algoritam je greedy algoritam za pronalaženje minimalnog razapinjućeg stabla (MST) u neusmerenom grafu sa težinama.

MST je podskup grana grafa koji:

• povezuje sve čvorove
• nema cikluse
• ima minimalnu moguću ukupnu sumu težina

Osnovna ideja

Kruskal bira grane po rastućoj težini i dodaje ih u stablo ako ne formiraju ciklus. Za proveru ciklusa koristimo DSU strukturu (Disjoint Set Union).

□ Ako još nisi radio DSU, pogledaj ovde: Struktura skupova — DSU (Union-Find)

1. Sortiraj sve grane po težini (od najmanje do najveće)
2. Prolazi kroz grane redom:
      ako grana NE pravi ciklus → dodaj u MST
      ako pravi ciklus → preskoči
3. Završetak: kada smo dodali (V-1) grana

Primer grafa (ASCII)

Graf sa 6 čvorova i težinama:

      (4)
 1 -------- 2
 |  \7      | \5
 |5   \     |   \
 |     \4   |2   \14
 3------ 4 -- 5 -- 6
     9       3

Grane zapisujemo kao (težina, u, v):

(2, 2, 5)
(3, 5, 6)
(4, 2, 4)
(5, 1, 3)
(5, 2, 6)
(7, 1, 4)
(9, 3, 4)
(14, 2, 6)

Sortirane grane → Kruskal će ih obrađivati tim redom.
Na kraju dobijamo MST sa minimalnom sumom težina.

Implementacija u C++

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

struct Edge {
    int w, u, v;
};

int find_set(int v, vector& parent){
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v], parent);
}

void union_sets(int a, int b, vector& parent, vector& rnk){
    a = find_set(a, parent);
    b = find_set(b, parent);
    if (a != b){
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
    }
}

int main(){
    int n = 6; // broj čvorova
    vector edges = {
        {4,1,2},{5,1,3},{7,1,4},{2,2,5},{5,2,6},{4,2,4},
        {9,3,4},{3,5,6},{14,2,6}
    };

    sort(edges.begin(), edges.end(), [](Edge &a, Edge &b){
        return a.w < b.w;
    });

    vector parent(n+1), rnk(n+1,0);
    for(int i=1;i<=n;i++) parent[i] = i;

    int mst_sum = 0;
    vector mst;

    for (auto &e : edges){
        if (find_set(e.u, parent) != find_set(e.v, parent)){
            union_sets(e.u, e.v, parent, rnk);
            mst.push_back(e);
            mst_sum += e.w;
        }
    }

    cout << "MST tezina = " << mst_sum << "\n";
    cout << "Grane u MST:\n";
    for (auto &e : mst)
        cout << e.u << " - " << e.v << " : " << e.w << "\n";

    return 0;
}

Zašto DSU?

Bez DSU morali bismo posle svake dodate grane da proveravamo da li smo formirali ciklus pretragom grafa (BFS/DFS), što bi bilo sporo.

DSU omogućava proveru ciklusa u amortizovano O(α(n)) vremenu, što je praktično konstantno.

Zadaci za vežbu

• Dati graf (10 čvorova, 15 grana) i odrediti MST po Kruskal algoritmu.
• Napisati program koji učitava graf i ispisuje MST.
• Pronaći protivprimer gde greedy izbor po najmanjoj težini po čvoru ne radi (ali Kruskal radi).
• Porediti vreme rada Kruskala i Prima na gustim i retkim grafovima.

Zaključak

Kruskal je idealan za grafove sa mnogo čvorova i relativno malo grana. Kombinacija sortiranja + DSU čini algoritam veoma brzim i efikasnim.

□ Preporučeno sledeće za učenje: Eulerovi putevi i ciklusi

Vraćanje na vodič za oblast "Grafovi i stabla"

← Mapa učenja — Grafovi i stabla