Kruskal’s Minimum Spanning Tree Algorithm in C++

A spanning tree is a subgraph of an existing graph that is a tree and connects all the nodes. There can be many spanning trees in a graph. Kruskal’s algorithm finds the minimum spanning tree, whose sum of weights of edges is minimum. You have to start by picking one by one the smallest weight between two nodes, that doesn’t create a cycle, and go on until all the nodes are included.

// Kruskal's Minimum Spanning Tree Algorithm

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define edgePair pair<int,int>

class Graph
{
    private:
        vector<pair<int, edgePair>> MyGraph;
        vector<pair<int, edgePair>> minSpanTree;
        int *parent;
        int nodes;
    public:
        Graph(int nodes);
        void AddWeightToEdge(int firstNode, int secondNode, int weight);
        int findSet(int i);
        void unionSet(int i, int j);
        void kruskalMinSpanTree();
        void printMinSpanTree();
};

Graph::Graph(int nodes)
{
    parent = new int[nodes];
    for (int i = 0; i < nodes; i++)
    {
        parent[i] = i;
    }
    MyGraph.clear();
    minSpanTree.clear();
}

void Graph::AddWeightToEdge(int firstNode, int secondNode, int weight)
{
    MyGraph.push_back(make_pair(weight, edgePair(firstNode, secondNode)));
}

int Graph::findSet(int i)
{
    if (i == parent[i])
    {
        return i;
    }
    else
    {
       return findSet(parent[i]);
    }
}

void Graph::unionSet(int i, int j)
{
    parent[i] = parent[j];
}

void Graph::kruskalMinSpanTree()
{
    int i, firstValue, secondValue;
    sort(MyGraph.begin(), MyGraph.end());
    for (i = 0; i < MyGraph.size(); i++)
    {
        firstValue = findSet(MyGraph[i].second.first);
        secondValue = findSet(MyGraph[i].second.second);
        if (firstValue != secondValue)
        {
            minSpanTree.push_back(MyGraph[i]);
            unionSet(firstValue, secondValue);
        }
    }
}

void Graph::printMinSpanTree()
{
    cout << "Node" << "\tWeight" << endl;
    for (int i = 0; i < minSpanTree.size(); i++)
    {
        char firstNode =  minSpanTree[i].second.first + 65;
        char secondNode = minSpanTree[i].second.second + 65;
        cout << firstNode << " - " << secondNode << ": " << minSpanTree[i].first;
        cout << endl;
    }
}
int main()
{
    int numberOfNodes = 5;
    Graph myGraph(numberOfNodes);
    myGraph.AddWeightToEdge(0, 1, 1);
    myGraph.AddWeightToEdge(0, 4, 4);
    myGraph.AddWeightToEdge(1, 0, 1);
    myGraph.AddWeightToEdge(1, 2, 7);
    myGraph.AddWeightToEdge(1, 4, 3);
    myGraph.AddWeightToEdge(2, 1, 7);
    myGraph.AddWeightToEdge(2, 3, 9);
    myGraph.AddWeightToEdge(2, 4, 5);
    myGraph.AddWeightToEdge(3, 2, 9);
    myGraph.AddWeightToEdge(3, 4, 2);
    myGraph.AddWeightToEdge(4, 0, 4);
    myGraph.AddWeightToEdge(4, 1, 3);
    myGraph.AddWeightToEdge(4, 2, 5);
    myGraph.AddWeightToEdge(4, 3, 2);
    myGraph.kruskalMinSpanTree();
    myGraph.printMinSpanTree();
    return 0;
}

Node    Weight
A - B: 1
D - E: 2
B - E: 3
C - E: 5