Your One-Stop Solution to Learn Kruskal Algorithm From Scratch

Kruskal’s algorithm is the concept that is introduced in the graph theory of discrete mathematics. It is used to discover the shortest path between two points in a connected weighted graph. This algorithm converts a given graph into the forest, considering each node as a separate tree. These trees can only link to each other if the edge connecting them has a low value and doesn’t generate a cycle in MST structure. In this tutorial, you will learn more about Kruskal Algorithm in detail.

Introduction to Kruskal Algorithm

As mentioned earlier, the Kruskal algorithm is used to generate a minimum spanning tree for a given graph. But, what exactly is a minimum spanning tree? A minimum spanning tree is a subset of a graph with the same number of vertices as the graph and edges equal to the number of vertices -1. It also has a minimal cost for the sum of all edge weights in a spanning tree.

Kruskal’s algorithm sorts all the edges in increasing order of their edge weights and keeps adding nodes to the tree only if the chosen edge does not form any cycle. Also, it picks the edge with a minimum cost at first and the edge with a maximum cost at last. Hence, you can say that the Kruskal algorithm makes a locally optimal choice, intending to find the global optimal solution. That is why it is called a Greedy Algorithm. 

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Creating Minimum Spanning Tree Using Kruskal Algorithm

You will first look into the steps involved in Kruskal’s Algorithm to generate a minimum spanning tree:

  • Step 1: Sort all edges in increasing order of their edge weights.
  • Step 2: Pick the smallest edge.
  • Step 3: Check if the new edge creates a cycle or loop in a spanning tree.
  • Step 4: If it doesn’t form the cycle, then include that edge in MST. Otherwise, discard it.
  • Step 5: Repeat from step 2 until it includes |V| - 1 edges in MST.

Using the steps mentioned above, you will generate a minimum spanning tree structure. So, now have a look at an example to understand this process better.

The graph G(V, E) given below contains 6 vertices and 12 edges. And you will create a minimum spanning tree T(V’, E’) for G(V, E) such that the number of vertices in T will be 6 and edges will be 5 (6-1).

Graph_for_Constructing_MST.

If you observe this graph, you’ll find two looping edges connecting the same node to itself again. And you know that the tree structure can never include a loop or parallel edge. Hence, primarily you will need to remove these edges from the graph structure.

Removing_Loops-OR-Parallel_Edges.

The next step that you will proceed with is arranging all edges in a sorted list by their edge weights.

The Edges of the Graph

Edge Weight

Source Vertex

Destination Vertex

E

F

2

F

D

2

B

C

3

C

F

3

C

D

4

B

F

5

B

D

6

A

B

7

A

C

8

After this step, you will include edges in the MST such that the included edge would not form a cycle in your tree structure. The first edge that you will pick is edge EF, as it has a minimum edge weight that is 2.

Edge_EF_Insertion.

Add edge FD to the spanning tree.

Edge_DF_Insertion

Add edge BC and edge CF to the spanning tree as it does not generate any loop.

/Edge_BCandCF_Insertion.

Next up is edge CD. This edge generates the loop in Your tree structure. Thus, you will discard this edge.

Discarding_Edge_CD

Following edge CD, you have edge BF. This edge also creates the loop; hence you will discard it.

Discaeding_Edge_BF.

Next up is edge BD. This edge also formulates a loop, so you will discard it as well.

Discarding_Edge_BD

Next on your sorted list is edge AB. This edge does not generate any cycle, so you need not include it in the MST structure. By including this node, it will include 5 edges in the MST, so you don’t have to traverse any further in the sorted list. The final structure of your MST is represented in the image below:

Kruskals_Algorithm-Minimum_Spanning_Tree.

The summation of all the edge weights in MST T(V’, E’) is equal to 17, which is the least possible edge weight for any possible spanning tree structure for this particular graph. Moving ahead, you will learn about implementing Kruskal algorithms using the Union Find Algorithm.

Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE CoursesEnroll Now
Stand Out From Your Peers this Appraisal Season

What Is Union Find Algorithm?

Union Find is an algorithm that keeps track of elements that are split into one or over one disjoint set. It has two primary operations: Find and Union. The Find operation returns the set of elements to which the given element (argument) belongs, whereas the Union operation merges two disjoint sets.

You need to divide the provided graph G(V, E) into three separate sets while building the Minimum Spanning Tree using Kruskal's approach. The first contains edge weight values, the second has a tree hierarchy for distinct nodes, and the third includes the rank of all nodes. By using Union and Find operations, it joins the distinct nodes which are treated as different trees themselves to formulate a minimum spanning tree. 

Implementation of Kruskal Algorithm

Any MST algorithm revolves around determining whether adding an edge would result in a loop or not. Union Find is the most popular algorithm for determining this. The Union-Find algorithm separates vertices into clusters, allowing you to determine whether two vertices belong to the same cluster and hence if adding an edge will produce a cycle.

The strategy to implement the Kruskal algorithm using Union-Find is given below:

  • Construct a structure to keep track of the source and destination nodes, as well as their weight.
  • Sort all the edges of a graph according to their edge-weight values.
  • Create three distinct sets to maintain nodes of a graph, their hierarchy in a tree, and corresponding ranks for every node.
  • Primarily, initialize all rank values to 0 and parent values to -1 (representing each node as its own tree itself).
  • For each insertion of an edge in MST, you will update the rank and parent of each node.
  • Do not insert the edge connecting two nodes if they have the same parent node, as this will cause a cycle in the tree structure.

Now, you will understand this implementation strategy with the help of an example. The graph for which you will develop a minimum spanning tree using Kruskal’s approach is given below:

Graph_for_Implementing_Kruskals_Algorithm.

Initially, you will need to create two sets for maintaining parent value and rank value for each node. Along with that, you will create a structure to keep the edges of the graph. For all the nodes in the graph, you will initialize parent values to -1 and rank values to 0. The reason behind that is that you need to treat all the nodes of a graph as trees themselves.

Initialising_Parent_and_Rank_set_values-Kruskals_Algorithm.

Additionally, remember that whenever you join two disjoint tree structures together, the rank of one being pointed to will increase by one. So, once you add edges into the MST, the rank and parent values of included nodes will change. This particular graph will show the state of sets, like the figure below.

Set_Updation-Kruskals_Algorithm.

The C program to implement Kruskal’s algorithm using above mentioned strategy is as follows:

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

//structure that denotes a weighted edge

struct Edge {

int source, destination, weight;

};

//structure that denotes a weighted, undirected and connected graph

struct Graph {

int Node, E;

struct Edge* edge;

};

//allocates memory for storing graph with V vertices and E edges

struct Graph* GenerateGraph(int Node, int E)

{

struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));

graph->Node = Node;

graph->E = E;

graph->edge = (struct Edge*)malloc(sizeof( struct Edge));

return graph;

}

//subset for Union-Find

struct tree_maintainance_set {

int parent;

int rank;

};

//finds the set of chosen element i using path compression

int find_DisjointSet(struct tree_maintainance_set subsets[], int i)

{

     //find root and make root as parent of i

if (subsets[i].parent != i)

subsets[i].parent

= find_DisjointSet(subsets, subsets[i].parent);

return subsets[i].parent;

}

//Creates the Union of two sets

void Union_DisjointSet(struct tree_maintainance_set subsets[], int x, int y)

{

int xroot = find_DisjointSet(subsets, x);

int yroot = find_DisjointSet(subsets, y);

  //connecting tree with lowest rank to the tree with highest rank

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

  //if ranks are same, arbitrarily increase the rank of one node

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

}

//function to compare edges using qsort() in C programming

int myComp(const void* a, const void* b)

{

struct Edge* a1 = (struct Edge*)a;

struct Edge* b1 = (struct Edge*)b;

return a1->weight > b1->weight;

}

//function to construct MST using Kruskal’s approach

void KruskalMST(struct Graph* graph)

{

int Node = graph->Node;

struct Edge

result[Node]; 

int e = 0; 

int i = 0; 

     //sorting all edges

qsort(graph->edge, graph->E, sizeof(graph->edge[0]),

myComp);

     //memory allocation for V subsets

struct tree_maintainance_set* subsets

= (struct tree_maintainance_set*)malloc(Node * sizeof(struct tree_maintainance_set));

     //V subsets containing only one element

for (int v = 0; v < Node; ++v) {

subsets[v].parent = v;

subsets[v].rank = 0;

}

     //Edge traversal limit: V-1

while (e < Node - 1 && i < graph->E) {

struct Edge next_edge = graph->edge[i++];

int x = find_DisjointSet(subsets, next_edge.source);

int y = find_DisjointSet(subsets, next_edge.destination);

if (x != y) {

result[e++] = next_edge;

Union_DisjointSet(subsets, x, y);

}

}

     //printing MST

printf(

"Edges created in MST are as below: \n");

int minimumCost = 0;

for (i = 0; i < e; ++i)

{

printf("%d -- %d == %d\n", result[i].source,

result[i].destination, result[i].weight);

minimumCost += result[i].weight;

}

printf("The Cost for created MST is : %d",minimumCost);

return;

}

int main()

{

int Node = 4; 

int E = 6; 

struct Graph* graph = GenerateGraph(Node, E);

     //Creating graph with manual value insertion

// add edge 0-1

graph->edge[0].source = 0;

graph->edge[0].destination = 1;

graph->edge[0].weight = 2;

}

// add edge 0-2

graph->edge[1].source = 0;

graph->edge[1].destination = 2;

graph->edge[1].weight = 4;

// add edge 0-3

graph->edge[2].source = 0;

graph->edge[2].destination = 3;

graph->edge[2].weight = 4;

// add edge 1-3

graph->edge[3].source = 1;

graph->edge[3].destination = 3;

graph->edge[3].weight = 3;

// add edge 2-3

graph->edge[4].source = 2;

graph->edge[4].destination = 3;

graph->edge[4].weight = 1;

// add edge 1-2

graph->edge[5].source = 1;

graph->edge[5].destination = 2;

graph->edge[5].weight = 2;

KruskalMST(graph);

return 0;

}

Output:

Kruskals_Algorithm_Program_Output

You can verify this output’s accuracy by comparing it with the MST structure shown above. The overall cost for this MST is 5.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Conclusion

In this lesson, you examined Kruskal Algorithm in the data structure. Kruskal's algorithm is used to construct the minimal spanning tree for a given graph topology. Additionally,  you also learned how to build an MST for a given graph using Kruskal's Algorithm. And finally, you saw how to develop this algorithm using the C programming language.

If you're seeking more in-depth training that goes past data structures and encompasses the fundamentals of interactive application development, Simplilearn's Software Development Courses will be ideal for you. The courses featured in this catalog will assist you in mastering the art of software development by shaping your understanding of programming languages.  Explore now and get started!

On that note, do you have any questions about this tutorial on Kruskal Algorithm? If you do, please leave them in the comments section at the bottom of this page; we will respond to them as soon as possible!

Happy learning!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.