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