C++ Program for Kruskal's Algorithm (to find MST of graph)

In this article, we would mainly be discussing the formation of a minimum spanning tree as well as the utilization of Kruskal’s algorithm for getting the minimum spanning tree of a graph. We would also be providing an implementation of Kruskal’s algorithm in C++ to help brush up on your concepts.

What is Kruskal’s Algorithm?

Graphs might just be one of the most difficult areas of programming to approach as a beginner. This is primarily because questions of data structures and algorithms in graphs are not very clear about how to proceed with a solution. It is only through rigorous practice that one can improve their knowledge of the algorithm. As it happens, one of the most popular algorithms used with graphs is the ones for traversing the graph in the minimum time possible as well as the ones which produce a minimum spanning tree from it. For graph traversal, we have the BFS and DFS algorithms, while the equivalent minimum spanning tree can be produced with the help of Prim’s algorithm or Kruskal’s algorithm.

These are some of the easiest algorithms which one can learn while they use graphs to solve problems. Minimum spanning trees help reduce the number of edges to a large extent so that only the minimal edges are shown. This, in turn, finds application in solving a variety of questions that can be solved using graphs. (The real difficulty for any beginner is to understand that graphs can be used to find a solution for a problem and how to manipulate the vertices and edges to their advantage.)

What is a Minimum spanning tree?

The main objective of using Kruskal’s algorithm is for getting the minimum cost spanning tree for a graph. However, this makes no sense if you don’t understand what a minimum spanning tree exactly is. This can be the best explaining with an example.

Let us suppose we have a graph like this:

We have four nodes, A, B, C, and D. We can rearrange the various edges of the graph to remove cycles and form a tree. This can be done in several ways:-

In this case, the weight of the tree is 22+21+13=56.

In this case, the weight of the tree is 10+22+21=53.

In this case, the weight of the tree is 10+18+13=41. On carefully comparing, we might see that this tree has the minimum weight amongst all of the trees obtained. The main objective for Prim’s algorithm or Kruskal’s algorithm is to obtain this minimum spanning tree. A tree obtained from a graph such that the sum of the weights of the edges is minimum is called a minimum spanning tree.

How Kruskal algorithm Works

The algorithm starts with V different groups (where V is the number of vertices in a graph). At every step of the process, the edge with the minimum weight of the graph is chosen and added to the minimum spanning tree. An edge is only chosen in such a way if it does not create a cycle – if the edge with the minimum weight causes a cycle in the minimum spanning tree, the algorithm proceeds with the edge with the second minimum weight. Adding an edge to the graph also merges both of the vertices making it into one group (remember that each of the vertices starts in separate groups initially). When the algorithm is finished, only one group is left which represents the minimum spanning tree.

C++ Kruskal’s algorithm works in a slightly different manner than Prim’s algorithm. Prim’s algorithm pushes vertices to this group and expands it one by one starting from the two vertices which form the edge with the minimum weight. Kruskal’s algorithm is more concerned with the edges rather than the vertices and deals with edges directly by adding their vertices to a common group.

There are two main ways of implementing Kruskal’s algorithm in C++: disjoint sets or priority queues. Using disjoint sets is slightly better as it helps visualize the change in the groups at any point in time.

The algorithm is as follows:-

1. Initialize an array for storing the groups of the vertices.
2. Initialize an array for storing the edges of the graph with their weights.
3. Initialize the spanning tree as an empty array.
4. Put all vertices of the graph into different groups.
5. Sort the array of edges in increasing order of weights.
6. Continue step 7 till there is no more edge remaining in the sorted array of edges
7. If the group of one node of an edge does not match the group of the other node of the edge, add them both to the same group and add the edge to the spanning tree array.
8. Iterate through the spanning-tree array and add the weights of the edges.
9. The sum of the edges thus obtained is the weight of the minimum spanning tree, while the spanning tree array contains the edges for the same.

Example

Let’s work out an example. Consider the above graph and let’s try to apply Kruskal’s algorithm to it.

Initially, we have to pick the first edge which has the minimum weight. AB is picked here, which weights 10.

Now, we pick the edge with the second minimum weight. CD is picked here since it weighs 13.

Proceeding further, we find that the edge with minimum weight is BC. The weight of this edge is 18.

Since a complete tree is obtained, we stop the algorithm here. The minimum weight for the tree thus obtained is 10+18+13=41.

C++ Program for Kruskal's Algorithm

The C++ implementation of Kruskal’s algorithm with the help of the union-find algorithm is given below. This is the source code of the C++ Krushkal Algorithm:-

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

using namespace std;
const int MAX = 1e6-1;
int root[MAX];
const int nodes = 4, edges = 5;
pair <long long, pair<int, int> > p[MAX];

int parent(int a)                                                       //find the parent of the given node
{
    while(root[a] != a)
    {
        root[a] = root[root[a]];
        a = root[a];
    }
    return a;
}

void union_find(int a, int b)                                         //check if the given two vertices are in the same “union” or not
{
    int d = parent(a);
    int e = parent(b);
    root[d] = root[e];
}

long long kruskal()
{
    int a, b;
    long long cost, minCost = 0;
    for(int i = 0 ; i < edges ; ++i)
    {
        a = p[i].second.first;
        b = p[i].second.second;
        cost = p[i].first;
        if(parent(a) != parent(b))                                  //only select edge if it does not create a cycle (ie the two nodes forming it have different root nodes)
        {
            minCost += cost;
            union_find(a, b);
        }
    }
    return minCost;
}

int main()
{
    int x, y;
    long long weight, cost, minCost;
    for(int i = 0;i < MAX;++i)                                       //initialize the array groups
    {
        root[i] = i;
    }
    p[0] = make_pair(10, make_pair(0, 1));
    p[1] = make_pair(18, make_pair(1, 2));
    p[2] = make_pair(13, make_pair(2, 3));
    p[3] = make_pair(21, make_pair(0, 2));
    p[4] = make_pair(22, make_pair(1, 3));
    sort(p, p + edges);                                             //sort the array of edges
    minCost = kruskal();
    cout << "Minimum cost is: "<< minCost << endl;
    return 0;
}

Output

The output for the given code segment is:

 Minimum cost is: 4

Conclusion

Our explanation of Kruskal’s algorithm and how it can be used to find a minimum spanning tree for a graph should prove to a useful tool in your preparation. The attached code also shows an implementation of Kruskal’s algorithm in C++.