0.

Kruskal’s Algorithm

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.

What is a Spanning Tree?

A spanning tree is a subset of a graph that includes all the graph's vertices and some of
the edges of the original graph, intending to have no cycles. A spanning tree is not
necessarily unique - it is possible for there to be multiple spanning trees for a given
graph. However, a given graph will always have at least one spanning tree. The edges
in a spanning tree are called "branch edges," while the edges not in the spanning tree
are called "cycle edges." And this type of graph helps find the minimum number of
edges required to connect all vertices in a graph. It is also used to create minimally
secured networks with redundant paths.

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-

weighted graph that connects all the vertices together without any cycles and with the
minimum possible total edge weight. It is a way of finding the most economical way to
connect a set of vertices. A minimum spanning tree is not necessarily unique. All the
weights of the edges in the MST must be distinct. If all the weights of the edges in the
graph are the same, then any spanning tree of the graph is an MST. The edges of the
minimum spanning tree can be found using the greedy algorithm or the more
sophisticated Kruskal or Prim's algorithm.

How Many Edges Does a Minimum Spanning Tree

Have?

A minimum spanning tree (MST) is a subset of the edges of a connected, undirected

graph that connects all the vertices with the most negligible possible total weight of the
edges. A minimum spanning tree has precisely n-1 edges, where n is the number of
vertices in the graph.

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).
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.
The next step that you will proceed with is arranging all edges in a sorted list by their
edge weights.

Source Destination Edge

Vertex Vertex Weight
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.
Add edge FD to the spanning tree.

Add edge BC and edge CF to the spanning tree as it does not generate any loop.
Next up is edge CD. This edge generates the loop in Your tree structure. Thus, you will
discard this edge.

Following edge CD, you have edge BF. This edge also creates the loop; hence you will
discard it.
Next up is edge BD. This edge also formulates a loop, so you will discard it as well.

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:
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.

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:

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.
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.

MST Construction Using Disjoint Sets

Graph

Vertices: {0, 1, 2, 3}
Sorted edges by weight:

1. (3, 2) → 1
2. (2, 1) → 2
3. (1, 0) → 2
4. (1, 3) → 3
5. (0, 2) → 4
6. (0, 3) → 4

Union–Find Rules (Union by Rank)

 find(x) returns the root of the set containing x.

 Union rule:
o If ranks are unequal, attach the lower-rank root under the higher-rank root (no
rank change).
o If ranks are equal, attach one root under the other and increase the new root’s
rank by 1.

Initialization
parent = [-1, -1, -1, -1]
rank = [ 0, 0, 0, 0]

Step 1: Process Edge (3, 2), weight = 1

 find(3) = 3, find(2) = 2 → different sets

 ranks equal (0 == 0) → rank increases

parent[3] = 2
rank[2] = 1

State:

parent = [-1, -1, -1, 2]

rank = [ 0, 0, 1, 0]

MST: {(3,2)}

Step 2: Process Edge (2, 1), weight = 2

 find(2) = 2, find(1) = 1 → different sets

  rank(2) > rank(1) → no rank increase

parent[1] = 2

State:

parent = [-1, 2, -1, 2]

rank = [ 0, 0, 1, 0]

MST: {(3,2), (2,1)}

Step 3: Process Edge (1, 0), weight = 2

 find(1) → 2, find(0) = 0 → different sets

 rank(2) > rank(0) → no rank increase

parent[0] = 2

State:

parent = [ 2, 2, -1, 2]
rank = [ 0, 0, 1, 0]

MST: {(3,2), (2,1), (1,0)}

Remaining Edges

 (1,3), (0,2), (0,3): both endpoints have the same root (2) → skipped (cycle)

Final MST

Edges: {(3,2), (2,1), (1,0)}

Total weight = 1 + 2 + 2 = 5

Key Correction (Important)

 Rank increases only once in this example: when (3,2) is added.

 Rank does NOT increase when adding (2,1) or (1,0) because the roots’ ranks are
unequal.
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:

Kruskal's vs Prim's Algorithm

Kruskal's Algorithm

Kruskal's greedy algorithm finds a minimum spanning tree for a weighted, undirected
graph. The algorithm starts with a forest consisting of the individual nodes of the graph
and then finds the cheapest edge from each node and adds it to the forest. This process
is repeated until only one tree is in the forest, the minimum spanning tree.
Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input
and finds the subset of the edges of that graph. This input forms a tree that includes
every vertex, where the total weight of all the edges in the tree is minimized. The
algorithm works by sorting the graph's edges by weight, then taking the edge with the
lowest weight from the graph and adding it to the tree. This process repeats until all the
vertices are included in the tree.

Prim's Algorithm

Prim's algorithm is also greedy and finds a minimum spanning tree for a weighted
undirected graph. However, the algorithm starts with a single node and then adds the
cheapest edge from that node to the tree. But Prim's algorithm works differently than
Kruskal's algorithm. And this process is repeated until there are n-1 edges in the tree,
where n is the number of nodes in the graph.

Kruskal's Algorithm Complexity

Kruskal's algorithm is a well-known algorithm for finding the minimum spanning tree of a
graph. It is a greedy algorithm that makes use of the fact that the edges of a minimum
spanning tree must form a subset of the edges of any other spanning tree.

The time complexity of Kruskal's Algorithm is O(ElogE), where E is the number of edges
in the graph. This complexity is because the algorithm uses a priority queue with a time
complexity of O(logE). However, the space complexity of the algorithm is O(E), which is
relatively high.