Algorytm Prima

Algorytm Prima wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, czyli znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to algorytm zachłanny.

int n,m,suma; //n to ilosc wierzcholkow, m to ilosc krawedzi, a suma to waga minimalnego drzewa rozpinajacego
 
vector< vector< pair<int,int> > > adj; //zbior krawedzi grafu
 
vector<bool> vis; //ta tablica znaczaco przyspiesza wykonanie (przechowuje informacje czy juz odwiedzilismy wierzcholek)
 
vector<int> waga, pi; //tablica wag, pi to reprezentacja drzewa
 
struct cmp{ //struktura uzywana z operatorem porownania dla kopca
    bool operator()(const int &a, const int &b){
        if(waga[a] < waga[b])return true;
        if(waga[a] > waga[b])return false;
        return a<b;
    }
};
 
set<int, cmp> kopiec;
 
void prim_dijkstra(int s){
 
    int v, u, c;
 
    waga.clear(); waga.resize(n, 1000000); //czyscimy tablice z wagami
 
    vis.clear(); vis.resize(n,false); //czyscimy pomocnicza tablice odwiedzen
 
    pi.resize(n);
 
    waga[s] = 0; pi[s]=s; //ustalamy wage wierzcholka poczatkowego na 0 i dodajemy krawedz s s do drzewa
 
    kopiec.clear(); //czyscimy kopiec
 
        for(int i=0; i<n; i++)kopiec.insert(i); //wypelniamy kopiec ktory teraz zawiera wszystkie wierzcholki
 
    while(!kopiec.empty()){ //dopoki kopiec nie jest pusty (stopniowo usuwamy z niego elementy i dodajemy do drzewa)
 
        u = *(kopiec.begin()); //bierzemy najmniejszy element z kopca (wierzcholek najblizej drzewa)
 
        kopiec.erase(kopiec.begin()); //usuwamy go z kopca
 
        vis[u]=true; //zaznaczmy ze juz odwiedzalismy wierzholek u
 
        for (int i=0; i<adj[u].size(); i++){ //sprawdzamy wszystkie krawedzie wychodzące z u
 
            v=adj[u][i].first; //v jest rowne wierzcholkowi do ktorego prowadzi dana krawedz z u
 
            if (!vis[v]){ //jezeli jeszcze nie odwiedzalismy v to ...
 
                c = adj[u][i].second; //c rowne jest wadze krawedzi u v
 
                if(c < waga[v]){ //jezeli krawedz wazy mniej niz aktualna minimalna waga dla krawedzi wierzcholka v to
 
                    kopiec.erase(kopiec.find(v)); //usuwamy wierzcholek v z kopca
 
                    waga[v]=c; //teraz minimalna waga krawedzi v jest krawedz u v
 
                    kopiec.insert(v); //dodajemy do kopca v
 
                    pi[v]=u; //dodajemy krawedz u v do drzewa
                }
            }
        }
        suma+=waga[u]; //zwiekszamy wage drzewa o wage dolączonej krawedzi
    }
}