Kruskal’s Algorithm Minimum Spanning Tree Complete Guide

Are you looking to understand Kruskal’s Algorithm to construct a Minimum Spanning tree for any given undirected or directed graph? In this article, I will provide a complete guide with code to understand Kruskal’s Algorithm.

A spanning tree of a connected and undirected graph is a subgraph that is a tree that binds all of the vertices together. Many different spanning trees can exist in a single graph.

What is Minimum Spanning Tree?

Minimum Spanning Tree[1] for any undirected or directed graph is a spanning tree with a weightless than or equal to the weight of every other spanning tree.

The weight of a spanning tree is the sum of weights provided to each of the edges of a spanning tree.

The greedy technique is used by Kruskal’s algorithm to find the minimum cost spanning tree. This approach treats the graph as a forest, with each node representing a separate tree. A tree can only link to another tree if it has the lowest cost of all the choices and does not violate the MST characteristics.

How many Minimum Edges does spanning Tree has?

To calculate the minimum number of edges for a spanning tree is easy. It has (V-1) where V is the number of vertices in the given graph.

Steps to find the Minimum Spanning Tree using Kruskal’s algorithm are as follows.

1. Arrange or Sort all of the edges in non-descending weight order.
2. Choose the smallest edge and Check to see if it forms a cycle with the spanning tree you've already created. Include this edge if a cycle isn't formed. Otherwise, toss it out.
3. Repeat step #2 until the spanning tree has (V-1) edges.]
Note: To perform step 2 you need to use Union-Find Algorithm for detection of Cycles. 

Let us See the Pseudocode for Kruskal’s algorithm

Let us some up the Kruskal’s minimum spanning algorithm using pseudocode and then I will discuss its implementation with actual code.

Algorithm minimumSpanningTree(graph G)
       S:= ∅
       for each vertex v in G.V do
           MAKE-SET(v)
       for each (u, v) in G.E ordered by weight(u, v), in increasing
           if FIND-SET(u) ≠ FIND-SET(v) then
                add{(u,v)} to set S
                UNION(FIND-SET(u), FIND-SET(v))
       return S
S = set of Edges

Working Code for Kruskal Algorithm

Let us see the working code implementation for Kruskal’s Algorithm in a real-world environment.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
// Defining a structure to store edge of the graph.
struct edge {
    int source, dest, weight;
};
 
// Defining a Structure for comparision of edges based on weights.
struct compare
{
    bool operator() (edge const &a, edge const &b) const {
        return a.weight > b.weight;
    }
};
 
// Creating a Class represeting disjoint set.
class disJointSet
{
    unordered_map<int, int> main;
public:
    // perform MakeSet operation on the given Graph
    void makeSet(int N)
    {
        // create `N` disjoint sets (one for each vertex)
        for (int i = 0; i < N; i++) {
            main[i] = i;
        }
    }
 
    // Find the root of the set in which element `k` belongs
    int Find(int k)
    {
        // if `k` is root
        if (main[k] == k) {
            return k;
        }
 
        // recursion for the parent node until we find the root
        return Find(main[k]);
    }
 
    // Perform Union of two subsets
    void Union(int a, int b)
    {
        // find the root of the sets in which elements
        // `x` and `y` belongs
        int x = Find(a);
        int y = Find(b);
 
        main[x] = y;
    }
};
 
// Function to construct S using Kruskal's algorithm
vector<edge> findKruskalSortPath(vector<edge> allEdges, int N)   
{
    // Initialize array s to stores the edges present in S
    vector<edge> S;
 
    // initialize `DisjointSet` class
    disJointSet ds;
 
    // create a singleton set for each element of the universe
    ds.makeSet(N);
 
    // sorting edges by increasing weight
    sort(allEdges.begin(), allEdges.end(), compare());
 
    // S contains exactly `V-1` edges
    while (S.size() != N - 1)
    {
        // consider the next edge with minimum weight from the graph
        edge next_edge = allEdges.back();
        allEdges.pop_back();
 
        // find the root of the sets to which two endpoints
        // vertices of the next edge belongs
        int x = ds.Find(next_edge.source);
        int y = ds.Find(next_edge.dest);
 
        // if both endpoints have different parents, they belong to
        // different connected components and can be included in S
        if (x != y)
        {
            S.push_back(next_edge);
            ds.Union(x, y);
        }
    }
    return S;
}
 
int main()
{
    // vector of graph edges as per the above diagram.
    vector<edge> allEdges =
    {
        // `(u, v, w)` triplet represent undirected edge from
        // vertex `u` to vertex `v` having weight `w`
        { 0, 1, 7 }, { 1, 2, 8 }, { 0, 3, 5 }, { 1, 3, 9 },
        { 1, 4, 7 }, { 2, 4, 5 }, { 3, 4, 15 }, { 3, 5, 6 },
        { 4, 5, 8 }, { 4, 6, 9 }, { 5, 6, 11 }
    };
 
    // Assign Total number of Nodes in the Graph.
    int N = 7;
 
    // construct graph
    vector<edge> e = findKruskalSortPath(allEdges, N);
 
    for (edge &currentedge: e)
    {
        cout << "(" << currentedge.source << ", " << currentedge.dest << ", "
             << currentedge.weight << ")" << endl;
    }
 
    return 0;
}

Output:

Kruskal's Algorithm Minimum Spanning Tree Complete Guide

Time Complexity:

For a graph with E edges and V vertices, Kruskal’s algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures.

Where E is the number of the Edges and V is the number of vertices present in the graph.

That is all for Kruskal’s Algorithm. Let me know if you have any questions in the comment section. Also, let me know if you want the code in a different language as well.

And please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Further Read:

  1. QuickSort in C++ Implementation and Examples
Share your love

2 Comments

Leave a Reply