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



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

← Mapa učenja — Grafovi i stabla