Kruskal’s Algorithm for MST

Introduction of Minimum Spanning Tree (MST):

It consists of three terms:

• Tree
• Spanning Tree
• Minimum Spanning Tree

First, we discuss all these 3 terms:

Tree: Tree is an acyclic connected graph. It means a graph without cycle and connected is known as tree.

Spanning Tree: A tree which contain all vertex of the given graph is known as spanning tree.

Minimum Spanning Tree: A Spanning tree whose overall cost is minimum is known as minimum spanning tree.

Minimum Spanning Tree is an important concept in graph theory and is widely studied in advanced data structures and algorithms subjects of the MCA course. Concepts like Kruskal’s Algorithm and Prim’s Algorithm help students understand real-world applications of graph algorithms in computer networks, routing, and optimization problems. Kruskal’s Algorithm is one of the most popular greedy algorithms used to find the Minimum Spanning Tree of a weighted graph efficiently.

Methods to Find MST:

To find MST of a given graph, we have two methods:

• Kruskal’s method
• Prim’s method

Kruskal’s Algorithm to Find MST:

Kruskal’s algorithm finds the minimum spanning tree using a greedy approach. This follows the minimum spanning tree of all properties. In this algorithm graph is treated as a forest and all nodes are treated as an individual tree. To find the minimum spanning tree with the help of Kruskal algorithm we will first choose a lowest cost edge and then again choose the lowest cost edge. This process will continue until all the vertex is added and together. Not even a cycle is produced. In this, only the lowest cost will choose the edge even if one vertex is not connected to the other vertex.

Algorithm:

1. Remove all the loops and all parallel edges.
   (Will separate all loops and parallel edges)
2. Arrange all edges in their increasing order of weight.
   (Will arrange all the edges in their increasing order weight.)
3. Add all edges which has the least weightage.
   (All edges will be connected, whose value or cost is the lowest.)

Example:

C Program to Implement Kruskal’s Algorithm:

#include <stdio.h>
#include <stdlib.h>

// Edge structure
typedef struct {
int src, dest, weight;
} Edge;

// Graph structure
typedef struct {
int V, E;
Edge* edges;
} Graph;

// Union-Find (Disjoint Set) structures
int* parent;
int* rank_arr;

// Create a graph with V vertices and E edges
Graph* createGraph(int V, int E) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->E = E;
graph->edges = (Edge*)malloc(E * sizeof(Edge));
return graph;
}

// Find set of an element (with path compression)
int find(int i) {
if (parent[i] != i)

parent[i] = find(parent[i]);
return parent[i];
}

// Union of two sets (by rank)
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);

if (rank_arr[rootX] < rank_arr[rootY]) {
parent[rootX] = rootY;
} else if (rank_arr[rootX] > rank_arr[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank_arr[rootX]++;
}
}

// Comparison function for qsort
int compareEdges(const void* a, const void* b) {
return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

// Kruskal's MST algorithm
void kruskalMST(Graph* graph) {
int V = graph->V;
Edge* result = (Edge*)malloc((V - 1) * sizeof(Edge));

// Sort edges by weight
qsort(graph->edges, graph->E, sizeof(Edge), compareEdges);

// Initialize Union-Find
parent = (int*)malloc(V * sizeof(int));
rank_arr = (int*)malloc(V * sizeof(int));

for (int v = 0; v < V; v++) {
parent[v] = v;
rank_arr[v] = 0;
}

int edgeCount = 0;
int i = 0;

// Pick edges until MST has V-1 edges
while (edgeCount < V - 1 && i < graph->E) {

Edge nextEdge = graph->edges[i++];

int x = find(nextEdge.src);
int y = find(nextEdge.dest);

// If including this edge doesn't form a cycle
if (x != y) {
result[edgeCount++] = nextEdge;
unionSets(x, y);
}
}

// Print the MST
printf("\nMinimum Spanning Tree:\n");
printf("Edge\t\tWeight\n");
printf("----\t\t------\n");

int totalWeight = 0;

for (i = 0; i < edgeCount; i++) {
printf("%d -- %d\t\t%d\n", result[i].src, result[i].dest, result[i].weight);
totalWeight += result[i].weight;
}

printf("\nTotal MST Weight: %d\n", totalWeight);

free(result);
free(parent);
free(rank_arr);
}

int main() {

int V = 6; // Number of vertices
int E = 9; // Number of edges

Graph* graph = createGraph(V, E);

// Add edges: (src, dest, weight)
graph->edges[0] = (Edge){0, 1, 4};
graph->edges[1] = (Edge){0, 2, 3};
graph->edges[2] = (Edge){1, 2, 1};
graph->edges[3] = (Edge){1, 3, 2};
graph->edges[4] = (Edge){2, 3, 4};
graph->edges[5] = (Edge){3, 4, 2};
graph->edges[6] = (Edge){4, 5, 6};
graph->edges[7] = (Edge){3, 5, 3};
graph->edges[8] = (Edge){2, 5, 5};

printf("Graph has %d vertices and %d edges\n", V, E);

kruskalMST(graph);

free(graph->edges);
free(graph);

return 0;
}

Frequently Asked Questions (FAQs)

Conclusion:

MST stands for minimum spanning tree. It is a tree having all graph edges whose weight is minimum and don’t form the cycle. To find MST from a given graph, we have two methods which are Prim’s method and Kruskal’s method. Kruskal method uses greedy approach to find MST of given graph.

---

Author
Mr. Rahul Agarwal
Associate Professor, Department of CS & IT
Biyani Group Of Colleges,Jaipur