Minimum Spanning Tree (MST) Using Kruskal Algorithm Explained with Real-Life Example

Introduction to Minimum Spanning Trees

In computer science and graph theory, one of the most practical and widely used concepts is the Minimum Spanning Tree (MST). It is heavily used in network design, road construction, electrical grid planning, telecommunications, and many optimization problems.

Among the algorithms used to find a Minimum Spanning Tree, Kruskal’s Algorithm is considered one of the simplest and most efficient.

If you are a student learning data structures and algorithms, understanding Kruskal’s Algorithm will help you solve many graph optimization problems.

In this blog, we will cover:

• What is a Minimum Spanning Tree?
• Why it is important
• Kruskal Algorithm explained step by step
• Real-world example
• C++ implementation
• Time complexity analysis
• Practical applications

What is a Graph?

A graph is a collection of:

• Vertices (Nodes) → Represent entities
• Edges → Represent connections between nodes

For example:

• Cities connected by roads
• Computers connected by cables
• Social media users connected by friendships

A weighted graph assigns a cost/weight to each edge.

Example:

If two cities are connected by a road of 50 km, then the edge weight is 50.

What is a Spanning Tree?

A spanning tree is a subset of a graph that:

✔ Connects all vertices
✔ Contains no cycles
✔ Has exactly V – 1 edges

Where V is the number of vertices.

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a spanning tree with the minimum possible total edge weight.

In simple words:

It connects all nodes using the least total cost.

Key Properties of MST

A Minimum Spanning Tree:

• Includes all vertices
• Has no loops/cycles
• Uses minimum total edge weight
• Contains exactly n – 1 edges

What is Kruskal Algorithm?

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree of a weighted graph.

It works by:

1. Sorting all edges by weight
2. Picking the smallest edge
3. Adding it if it does not form a cycle
4. Repeating until MST is complete

The algorithm always chooses the cheapest available edge.

Why is it Called a Greedy Algorithm?

A greedy algorithm makes the best local choice at each step hoping it leads to the optimal overall solution.

In Kruskal Algorithm:

At every step, we choose the minimum weight edge.

Real-Life Scenario of Kruskal Algorithm

Scenario: Internet Network Installation for a University Campus

Suppose a university wants to connect 5 buildings:

• Admin Block
• Library
• Computer Lab
• Hostel
• Cafeteria

The installation costs between buildings are:

The goal:

Connect all buildings with minimum total wiring cost.

This is solved using Kruskal Algorithm.

Step-by-Step Working of Kruskal Algorithm

Step 1: Sort Edges by Weight

Sorted order:

Step 2: Select Minimum Edge

Pick:

Admin – Library (2)

No cycle formed.

Step 3: Pick Next Minimum Edge

Library – Lab (3)

No cycle.

Step 4: Pick Next Edge

Hostel – Cafeteria (4)

No cycle.

Step 5: Pick Next Edge

Lab – Hostel (5)

Connects all components.

Final MST

Selected edges:

• Admin – Library → 2
• Library – Lab → 3
• Hostel – Cafeteria → 4
• Lab – Hostel → 5

Total Cost

2 + 3 + 4 + 5 = 14

This is the Minimum Spanning Tree.

How Kruskal Detects Cycles?

Kruskal uses a data structure called Disjoint Set Union (DSU) or Union-Find.

It helps:

• Track connected components
• Detect cycles efficiently

Operations:

Find()

Checks which set a node belongs to.

Union()

Merges two sets.

If two vertices already belong to the same set, adding that edge forms a cycle.

ruskal Algorithm Steps

Here is the complete procedure:

Step 1

Sort all edges in ascending order

Step 2

Initialize each vertex as separate set

Step 3

Pick smallest edge

Step 4

Check cycle using Union-Find

Step 5

If no cycle, add edge

Step 6

Repeat until MST contains V – 1 edges

C++ Implementation of Kruskal Algorithm

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
        int src, dest, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

class DSU {
    vector<int> parent;
    public:
    DSU(int n) {
        parent.resize(n);
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};

void kruskal(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end(), compare);

    DSU dsu(V);

    int mstCost = 0;

    cout << "Edges in MST:\n";

    for(auto edge : edges) {
        if(dsu.find(edge.src) != dsu.find(edge.dest)) {
            dsu.unite(edge.src, edge.dest);
            cout << edge.src << " - " << edge.dest
                    << " : " << edge.weight << endl;
            mstCost += edge.weight;
        }
    }

    cout << "Minimum Cost: " << mstCost << endl;
}

int main() {
    int V = 5;

    vector<Edge> edges = {
            {0,1,2},
            {1,2,3},
            {3,4,4},
            {2,3,5},
            {0,2,6},
            {2,4,7},
            {1,3,8}
    };

    kruskal(edges, V);

    return 0;
}

Sample Output:

Edges in MST:
0 – 1 : 2
1 – 2 : 3
3 – 4 : 4
2 – 3 : 5
Minimum Cost: 14

Time Complexity of Kruskal Algorithm

The complexity mainly depends on sorting.

Sorting Edges

O(E log E)

Union-Find Operations

Nearly O(1)

Overall Complexity

O(E log E)

Where:

• E = Number of edges
• V = Number of vertices

This makes Kruskal efficient for sparse graphs.

Advantages of Kruskal Algorithm

Simple to Understand

Easy to implement

Efficient

Works well for sparse graphs

Optimal Solution

Always finds MST

Practical

Used in real-world network optimization

Disadvantages of Kruskal Algorithm

Sorting Overhead

Sorting large edge lists can be expensive

Less Efficient for Dense Graphs

Prim’s Algorithm may perform better

Kruskal vs Prim’s Algorithm

Practical Applications of Kruskal Algorithm

Network Design

Connecting computers with minimum cable cost

Road Construction

Building roads between cities cheaply

Electrical Grids

Connecting substations

Water Supply Systems

Optimizing pipeline layouts

Cluster Analysis

Used in machine learning

Common Interview Questions

1. What is Minimum Spanning Tree?

A tree connecting all vertices with minimum total edge weight.

2. Why does Kruskal use Union-Find?

To detect cycles efficiently.

3. Is Kruskal greedy?

Yes.

It always chooses the minimum edge.

4. Can MST have multiple solutions?

Yes, if multiple edges have equal weights.

Tips for Students

When solving MST problems:

✔ Sort edges carefully
✔ Check for cycles
✔ Stop after selecting V-1 edges
✔ Practice Union-Find implementation

Final Thoughts

Kruskal Algorithm is one of the most elegant graph algorithms in computer science.

It demonstrates how a simple greedy strategy can solve complex optimization problems efficiently.

Whether designing:

• Communication networks
• Road systems
• Electrical circuits

Kruskal Algorithm helps minimize cost while ensuring complete connectivity.

For students preparing for exams, coding interviews, or competitive programming, mastering Kruskal Algorithm is essential.

Start by understanding the real-life intuition, then practice coding it multiple times.

That is the fastest way to master Minimum Spanning Trees using Kruskal Algorithm.