Kruskal's Algorithm

Introduction

A Graph is a data structure consisting of edges connecting vertices. When all the vertices of a graph are connected such that there is no cycle and the number of edges is (v-1)  ( where v is the number of vertices of the graph), the weighted tree formed is called a spanning tree

A single graph can have more than one spanning tree, and the spanning tree with the minimum sum of all edge weights is called the minimum spanning tree

There are various algorithms to find the minimum spanning tree of a graph. One such algorithm is Prims Algorithm. In this article, we’ll learn about another algorithm to find the minimum spanning tree. This algorithm is known as Kruskal’s minimum spanning tree.

So let’s get started!

Problem Statement

The problem states that “Given a connected and undirected graph, find its minimum spanning tree using Kruskal’s minimum spanning tree algorithm.” 

 

Note: A graph having bidirectional edges is known as an undirected graph. Such graphs can be traversed in either direction.

 

Let’s understand the problem statement with the help of an example.

 

Given a graph having Number of vertices(V) = 5, and Number of edges(E) = 6. Cost of an edge and the vertices having the edge are(cost, vertex1, vertex2): ( 2,0,1) , (1,4,3), (3,1,2), (2,4,2), (3,2,3), (1,1,4). 

 

The graph contains five vertices and six edges. So the minimum spanning tree will have four edges. The diagram below shows the graph and its minimum spanning tree.









Above is the graph









Above is the corresponding minimum spanning tree

 

Edges of the minimum spanning trees are: (1,4), (4,3), (0,1), (4,2). And, the total weight of the tree will be 6. 

 

Now, let's move on to the solution approach of this problem.

Solution Approach

Kruskal’s minimum spanning tree algorithm is a greedy approach because we pick the smallest edge. We're making that choice because we want our spanning tree to have a minimum total sum of edges. 

 

A graph may or may not contain a cycle. But in MSP, we need to ensure that there is no cycle. So, in this algorithm, we're using a disjoint data structure to find if two nodes are in the same subset or not. This will help detect a cycle

 

Want to know what a disjoint set data structure is?

 

  • A disjoint set data structure is used to track the division of elements into different disjoint subsets. 
  • The union-find algorithm performs two operations on this data structure, namely, find and union. For more details, you can refer to this blog.

 

The steps of Kruskal’s algorithm are as follows :

 

  1. Sort all the edges in ascending order based on their weights.

 

  1. Draw the edge with the least weight. Check if it generates a cycle with the spanning-tree formed till now using a union-find algorithm. If the cycle is not formed, include this edge. Else, discard it and move to the next.

 

  1. Repeat step 2 until there are (v-1) edges in the spanning tree. 

 

Let’s understand this algorithm using the above example : 





The graph contains five vertices and six edges. So, the minimum spanning tree will have (5-1) = four edges. We'll be performing one step at a time and understand how that'll work.

 

Step 1:  After sorting the edges in increasing order of their weights, we get : 

 

WeightEdge(between the vertices)

1

1 - 4

1

4 - 3

2

0 - 1

2

4 - 2

3

1 - 2

3

2 - 3

 

Step 2: Now, we start picking edges one by one until we get four edges of our spanning tree. Currently, our spanning tree has no edges. 

 

  • Pick edge 1 - 4: It doesn't form any cycle, so add it.




 

  • Pick edge 4-3: It doesn't form any cycle, so add it.



 

  • Pick edge 0-1: It doesn't form any cycle, so add it.



 

  • Pick edge 4-2: It doesn't form any cycle, so add it.



 

At this point, we've already taken four edges in our spanning tree, and therefore, we stop, and our spanning tree is complete and has the minimum weight.

 

We have taken the edges 1 - 4, 4 - 3, 0 - 1, and 4 - 2. Thus, the total weight of the minimum spanning tree is 1+1+2+2 = 6

 

You’ve now understood the working and the reasoning behind using Kruskal’s minimum spanning tree algorithm to find the minimum spanning tree. 

 

Let’s work on the implementation now!

 

Before directly jumping to the solution, we suggest you try and solve this problem on Codestudio.

Implementation

Let’s see the implementation of the above approach.

 

#include<bits/stdc++.h>

using namespace std;

 

const int MAX = 1e6-1;

int parent[MAX];

 

int find(int a){  //function to find the parent of the subset this a belongs to

    while(parent[a]!=a){

        parent[a] = parent[parent[a]];

        a = parent[a];

    }

    return a;

}

 

void union_(int a,int b){  //function to merge two subsets

    int d = find(a);

    int e = find(b);

    parent[d] = parent[e];

}

 

int main(){

    int vertices;

    cin>>vertices;

    int edges;

    cin>>edges;

    vector<pair<int,pair<int,int>>>adj;      // vector to store the edges in the form - > {weight, {source, destination}}

    for(int i=0;i<edges;i++){

        int weight;

        int src,destination;

        cin>>weight>>src>>destination;

        adj.push_back({weight,{src,destination}});   // pushing back the edges one by one

    }

    sort(adj.begin(),adj.end());     // sorting the edges 

    for(int i = 0;i<MAX;i++){

        parent[i] = i;        // initialising the parent of each node as itself

    }

    vector<pair<int,int>>tree_edges;      // vector for storing the edges of the minimum spanning tree

    int totalweight = 0;     //initialising the total weight to 0

    for(auto x:adj){

        int a = x.second.first;

        int b = x.second.second;

        int cost = x.first;

        if(find(a)!=find(b)){        // if the two vertices are in different subsets, merge them into one

            totalweight+=cost;

            union_(a,b);

            tree_edges.push_back({a,b});

        }

    }

    cout<<"Edges are : "<<endl;

    for(auto x:tree_edges){  // printing the edges of the minimum spanning tree

        cout<<x.first<<" "<<x.second<<endl;

    }

    cout<<"Total weight of MST = ";

    cout<<totalweight<<endl;        //printing the total weight of the minimum spanning tree

    return 0;

}

 

Input

 

//entering the number of vertices

5

//entering the number of edges

6

//entering edges one by one in the format: cost, v1, v2

2 0 1

1 4 3

3 1 2

2 4 2

3 2 3

1 1 4

 

Output

 

//Output

Edges are :

1 4

4 3

0 1

4 2

Total weight of MST = 6

 

Time Complexity

The time complexity of Kruskal's minimum spanning tree algorithm is O(E*logV), where E is the number of edges in the graph and V is the number of vertices.

 

Reason: Since we're sorting the edges, which takes O(E*logE) time. Then we check for each edge whether to add it or not by using the union-find algorithm, which takes at most O(logV) time for every edge E, Hence total O(ElogV). 

 

Thus the overall complexity will be O(ElogE + ElogV), which is approximately O(ElogV).

 

Space Complexity

The space complexity of Kruskal's minimum spanning tree algorithm is O(|E| + |V|), where E is the number of edges in the graph and V is the number of vertices. 

 

Reason: Since disjoint set structure takes O(|V|) space to store the parents of vertices and O(|E|), since we’re additionally storing the edges of the graph. 

 

If you've made it this far, congratulations, Champ! You've understood the Kruskal’s minimum spanning tree algorithm”. If you haven't already submitted it to CodeStudio. Without further ado, have it accepted as early as possible.

 

You must watch this video for the conceptual understanding and proper code implementation of the “Kruskal’s Algorithm”.

Frequently asked questions
 

  1. What is Kruskal’s minimum spanning tree?
    The tree formed using Kruskal's minimum spanning tree algorithm on a graph is called the minimum spanning tree.
     
  2. What is a spanning tree?
    A spanning tree of a Graph G is its subset, having all the vertices covered with the minimum possible number of edges. Thus, a spanning tree has v-1 edges. 
     
  3. What is a minimum spanning tree?
    A spanning tree with a minimum sum of all edges among all the spanning trees of a graph is called the minimum spanning tree.
     
  4. What is Kruskal’s algorithm used for?
    Kruskal’s algorithm is used for finding the minimum spanning tree of a graph. 
     
  5. What are minimum spanning trees used for?
    For network architectures, minimum spanning trees are utilized (i.e. telephone or cable networks). They're also utilized to develop approximate solutions to complex mathematical issues like the Traveling Salesman Problem.

 

Key Takeaways

In this article, we've discussed Kruskal’s minimum spanning tree algorithm here, along with its approach and implementation in C++.

Other similar algorithms are Prim’s algorithm using minimum spanning tree and The travelling salesman problem. Don't forget to try it out, as it'll help you empower your understanding. 

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and overview student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes