kruskal.cpp

#include <iostream>
#define V 5 // pet verteksa
using namespace std;

int roditelj[V];

int pronadji(int i) { //najdi krajnjeg roditelja cvora
    while(roditelj[i] != i) {
        i = roditelj[i];
    }
    return i;
}

void spoji(int i, int j) { //combine i and j,
// returns false if i and j are already in same set
    int a = pronadji(i);
    int b = pronadji(j);
    roditelj[a] = b;
}

void kruskalMST(int graf[][V]) {
    int minCostStablo = 0; //cijena najjeftinijeg razapinjuceg stabla

    for (int i=0; i < V; i++) //na pocetku nitko nema roditelja
        roditelj[i] = i;

    int br_veza = 0, x, y;
    cout << "Ispis veza: " << endl;
    //trazi najjeftinije veze jednu po jednu
    while (br_veza < V-1) {
        int minCostVeza = INT_MAX;
        for (int i=0;i<V;i++) { //idi po svim mogucim vezama
            for (int j=0;j<V;j++) {
                if(pronadji(i) != pronadji(j) && graf[i][j] < minCostVeza) {
                    minCostVeza = graf[i][j];
                    x = i;
                    y = j;
                }
            }
        }
        spoji(x, y);
        br_veza++;
        cout << br_veza << ". veza: (" << x <<  ", " << y << ") = " << minCostVeza << endl;
        minCostStablo += minCostVeza;
    }
    cout << endl << "MST cijena: " << minCostStablo << endl;
}

int main() {



    int graf[V][V] =
    {
	{0, 2, 0, 6, 0},
    {2, 0, 3, 8, 5},
    {0, 3, 0, 0, 7},
    {6, 8, 0, 0, 9},
    {0, 5, 7, 9, 0}
	};
    cout << "Kruskalov algoritam" << endl;
    cout << "-------------------" << endl;
    for (int i=0;i<V;i++) {
        for (int j=0;j<V;j++) {
            cout << graf[i][j] << " ";
        }
        cout << endl;
    }
    cout << "-------------------" << endl;
    //zamijeni nule s INT_MAX;
    for (int i=0;i<V;i++) {
        for (int j=0;j<V;j++) {
            if(graf[i][j] == 0) graf[i][j] = INT_MAX;
        }
    }
    kruskalMST(graf);
    return 0;
}

//each time select a minimum cost edge
//if the selection forms a cycle (spanning tree is without cycles) don't include it in the solution