MST — Primov algoritam
Primov algoritam pronalazi minimalno razapinjuće stablo (MST) u povezanim neusmerenim grafovima sa težinama. Za razliku od Kruskala, koji bira grane po težini, Prim gradi MST tako što polazi od jednog čvora i širi se ka ostalim čvorovima.
Ovo je greedy algoritam — u svakom koraku bira se najjeftinija grana kojom se dodaje novi čvor u stablo.
Osnovna ideja algoritma
1. Izaberi početni čvor (npr. čvor 1)
2. Dodaj sve njegove grane u prioritetski red (min heap)
3. Dok MST ne sadrži sve čvorove:
a) uzmi najkraću dostupnu granu
b) ako vodi do čvora koji NIJE u MST → prihvati je
c) dodaj nove grane koje polaze iz tog čvora u red
Prioritetski red (min-heap) nam uvek daje trenutnu najjeftiniju granu.
Primer grafa (ASCII)
4
1 ------- 2
| \7 | \5
5 | \ |2 \14
| \4 | \
3---- 4 -- 5 -- 6
9 3
Počinjemo od čvora 1:
Najkraća grana iz čvora 1 je (1 - 3) = 5 → dodajemo u MST.
Slično, korak po korak dodajemo najkraće dostupne grane u stablo dok svi čvorovi ne budu uključeni.
Implementacija u C++ (sa priority_queue)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
int n = 6; // broj čvorova
vector>> graf(n+1);
// unos grafa (u,v,w)
vector> edges = {
{1,2,4},{1,3,5},{1,4,7},{2,5,2},{2,6,5},{2,4,4},
{3,4,9},{5,6,3},{2,6,14}
};
for (auto &[u,v,w] : edges){
graf[u].push_back({v,w});
graf[v].push_back({u,w});
}
vector uMST(n+1, false);
priority_queue<
pair,
vector>,
greater>
> pq; // (tezina, cvor)
pq.push({0, 1}); // krećemo od čvora 1
int mst_sum = 0;
while (!pq.empty()){
auto [w, u] = pq.top(); pq.pop();
if (uMST[u]) continue;
uMST[u] = true;
mst_sum += w;
for (auto &p : graf[u]){
int v = p.first, cost = p.second;
if (!uMST[v]) pq.push({cost, v});
}
}
cout << "MST ukupna tezina = " << mst_sum << endl;
return 0;
}
Prednosti i kada koristiti Prim
| Prednosti | Kada je najbolji izbor |
|---|---|
| Efikasan uz priority queue | Kod gustih grafova (mnogo grana) |
| Lako se implementira sa adjacency listama | Kod mreža, mapa, puteva |
| Pogodan za real-time probleme | Kada je grafa već delimično MST |
Poređenje — Prim vs Kruskal
| Prim | Kruskal |
|---|---|
| Polazi iz jednog čvora i širi se | Bira globalno najmanje grane |
| Radi uz priority queue | Potreban je DSU (Union-Find) |
| Bolji za guste grafove | Bolji za retke grafove |
| Ne zahteva sortiranje svih grana | Sortira sve grane unapred |
Zadaci za vežbu
- Napisati program koji učitava graf i ispisuje MST koristeći Primov algoritam.
- Porediti ukupan zbir MST težina za Prim i Kruskala na istom grafu.
- Probati oba algoritma na matrici susedstva i listi susedstva — uporediti brzinu.
- Prim na matrici labirinta — pronaći najjeftiniji put spajanja tačaka.
Zaključak
Prim i Kruskal su najčešće korišćeni algoritmi za izgradnju MST. Oba su greedy, ali koriste različite strategije.
□ Preporučeno sledeće za učenje: Grafovi MST - Kruskalov algoritam