kruskal_MST.txt

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> parent;
vector<int> ranks;

int graph[6][3] = {{0,2,4},{0,1,3},{1,3,2},{1,5,1},{3,4,6},{2,4,5}};

void init_rank()
{
    parent.resize(10);
    ranks.resize(10);

    for (int i = 0; i < 10; i++) {
        parent[i] = i;
        ranks[i] = 0;
    }
}

int find_parent(int x)
{
    if (parent[x] != x)
        parent[x] = find_parent(parent[x]);
    return parent[x];
}

void union_nodes(int x, int y)
{
    int xroot = find_parent(x);
    int yroot = find_parent(y);

    if (xroot != yroot) {
        if (ranks[xroot] > ranks[yroot]) {
            parent[yroot] = xroot;
        } else if (ranks[xroot] < ranks[yroot]) {
            parent[xroot] = yroot;
        } else {
            parent[xroot] = yroot;
        }
    }
}

struct edge {
    int u;
    int v;
    int w;

    bool operator<(edge &e) {
        return w < e.w;
    }
};

bool f(vector<int> &first, vector<int> &second)
{
    return first[2] < second[2];
}

int main()
{
    vector<vector<int>> edges(6);
    init_rank();

    for (int i = 0; i < 6; i++) {
        edges[i].push_back(graph[i][0]);
        edges[i].push_back(graph[i][1]);
        edges[i].push_back(graph[i][2]);
    }

    sort(edges.begin(), edges.end(), f);
    cout << "sorting done" << endl;

    for (int i = 0; i < 6; i++) {
        for (int x : edges[i]) {
            cout << x << " ";
        }
        cout << endl;
    }

    vector<struct edge> mst;

    for (int i = 0; i < 6; i++) {
        vector<int> temp_edge = edges[i];
        if (find_parent(temp_edge[0]) != find_parent(temp_edge[1])) {
            union_nodes(temp_edge[0], temp_edge[1]);
            struct edge temp;
            temp.u = temp_edge[0];
            temp.v = temp_edge[1];
            temp.w = temp_edge[2];
            mst.push_back(temp);
        }
    }

    cout << "MST - " << endl;

    while(!mst.empty()) {
        struct edge temp = mst.back();
        mst.pop_back();
        cout << "edge - " << temp.u << " " << temp.v << " " << temp.w << endl;
    }

    return 0;
}