implementation of kruskal's algorithm in C++

// C++ program for Kruskal's algorithm to find Minimum

// Spanning Tree of a given connected, undirected and

// weighted graph

#include<bits/stdc++.h>

using namespace std;

// Creating shortcut for an integer pair

typedef  pair<int, int> iPair;

// Structure to represent a graph

struct Graph

{

    int V, E;

    vector< pair<int, iPair> > edges;

    // Constructor

    Graph(int V, int E)

    {

        this->V = V;

        this->E = E;

    }

    // Utility function to add an edge

    void addEdge(int u, int v, int w)

    {

        edges.push_back({w, {u, v}});

    }

    // Function to find MST using Kruskal's

    // MST algorithm

    int kruskalMST();

};

// To represent Disjoint Sets

struct DisjointSets

{

    int *parent, *rnk;

    int n;

    // Constructor.

    DisjointSets(int n)

    {

        // Allocate memory

        this->n = n;

        parent = new int[n+1];

        rnk = new int[n+1];

        // Initially, all vertices are in

        // different sets and have rank 0.

        for (int i = 0; i <= n; i++)

        {

            rnk[i] = 0;

            //every element is parent of itself

            parent[i] = i;

        }

    }

    // Find the parent of a node 'u'

    // Path Compression

    int find(int u)

    {

        /* Make the parent of the nodes in the path

           from u--> parent[u] point to parent[u] */

        if (u != parent[u])

            parent[u] = find(parent[u]);

        return parent[u];

    }

    // Union by rank

    void merge(int x, int y)

    {

        x = find(x), y = find(y);

        /* Make tree with smaller height

           a subtree of the other tree  */

        if (rnk[x] > rnk[y])

            parent[y] = x;

        else // If rnk[x] <= rnk[y]

            parent[x] = y;

        if (rnk[x] == rnk[y])

            rnk[y]++;

    }

};

 /* Functions returns weight of the MST*/

int Graph::kruskalMST()

{

    int mst_wt = 0; // Initialize result

    // Sort edges in increasing order on basis of cost

    sort(edges.begin(), edges.end());

    // Create disjoint sets

    DisjointSets ds(V);

    // Iterate through all sorted edges

    vector< pair<int, iPair> >::iterator it;

    for (it=edges.begin(); it!=edges.end(); it++)

    {

        int u = it->second.first;

        int v = it->second.second;

        int set_u = ds.find(u);

        int set_v = ds.find(v);

        // Check if the selected edge is creating

        // a cycle or not (Cycle is created if u

        // and v belong to same set)

        if (set_u != set_v)

        {

            // Current edge will be in the MST

            // so print it

            cout << u << " - " << v << endl;

            // Update MST weight

            mst_wt += it->first;

            // Merge two sets

            ds.merge(set_u, set_v);

        }

    }

    return mst_wt;

}

// Driver program to test above functions

int main()

{

    /* Let us create above shown weighted

       and unidrected graph */

    int V = 9, E = 14;

    Graph g(V, E);

    //  making above shown graph

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

    cout << "Edges of MST are \n";

    int mst_wt = g.kruskalMST();

    cout << "\nWeight of MST is " << mst_wt;

    return 0;

}

Edges of MST are

          6 - 7

          2 - 8

          5 - 6

          0 - 1

          2 - 5

          2 - 3

          0 - 7

          3 - 4

         

          Weight of MST is 37