Minimum Spanning Tree (MST) | Kruskal’s Algorithm in C++

Introduction

A Spanning tree of a graph is a subgraph that includes all the vertices of the original graph while forming a tree structure (no cycles).

What is a Minimum spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected weighted graph that connects all the vertices with the minimum possible total edge weight. The objective of finding an MST is to minimize the total weight of the tree. The sum of the weights of the edges in the MST should be as small as possible.
In simpler terms, it is a tree that spans all the vertices of a graph with the least amount of edge weight.

Minimum Spanning Tree (MST) Applications

• Network Design: MSTs can be used to design efficient networks, such as electrical grids, communication networks, or transportation systems, by minimizing the cost or distance required to connect all the nodes.
• Cluster Analysis: MSTs can be employed in clustering algorithms to group similar data points together while minimizing the total distance or dissimilarity within each cluster.

To find a Minimum Spanning Tree, there are popular algorithms like Kruskal’s Algorithm and Prim’s Algorithm that can be used. These algorithms iteratively select edges with the smallest weights to construct the MST. Both of these algorithms use Greedy-Approach to find the Minimum Spanning Tree.
In this post, we’ll be discussing Kruskal’s Algorithm for Minimum Spanning Tree (MST).

Note: Since both of these algorithms use a greedy approach, they don’t guarantee the most optimum solution.

Kruskal’s algorithm

Kruskal’s algorithm is one of the popular algorithms used to find an MST in a connected weighted graph. This algorithm is efficient, easy to understand, and guarantees the construction of a minimum-weight spanning tree. In this blog post, we will explore Kruskal’s algorithm in detail and provide a C++ implementation.

Explanation

Kruskal’s algorithm follows a greedy approach to construct an MST. The basic idea is to select edges in ascending order of their weights while avoiding the formation of cycles. Here’s a step-by-step overview of the algorithm:

1. Sort all the edges of the graph in non-decreasing order of their weights.
2. Create an empty set to store the MST.
3. Iterate over the sorted edges and consider each edge one by one.
   • If adding the current edge to the MST does not form a cycle, add it to the MST.
   • To check for cycles, we can use the Disjoint Set Union (DSU) data structure.
4. Continue this process until we have (V – 1) edges in the MST, where V is the number of vertices in the graph.

Pseudocode

Kruskal (G)
MST = NULL
for each v ∈ G[vertices]:
 Make-Set (v)
sort G[edges] in non-decreasing order of weight w
for each edge(u, v) ∈ G[edges]:
 if connected(u, v) = false
  MST = MST ∪ {u, v}
  Union(u, v)
return MST

Code Implementation

//
//  main.cpp
//  Kruskal's Algorithm
//
//  Created by Himanshu on 28/05/23.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Data structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};

// Comparator function to sort edges based on their weights
bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

// Utility function for finding id of DSU (Disjoint Set Union) member
int getRoot (int i, int id[]) {
     
    while (i != id[i]) {
        i = id[i];
    }
    
    return i;
}

// Connected operation of DSU (Disjoint Set Union) data structure
bool connected (int p, int q, int id[]) {
    return (getRoot(p, id) == getRoot(q, id));
}
 
// Union operation of DSU
void unionSet (int p, int q, int *id) {
    int i = getRoot(p, id);
    int j = getRoot(q, id);
     
    id[i] = j;
}

// Kruskal's algorithm for finding MST
vector<Edge> kruskalMST(vector<Edge>& edges, int V) {
    vector<Edge> MST; // to store the MST
    
    int *id = new int[V];
     
    for (int i=0; i<V; i++) {
        id[i] = i;
    }

    // Sort the edges based on their weights
    sort(edges.begin(), edges.end(), compareEdges);

    int count = 0;
    int i = 0;
    while (count < V - 1 && i < edges.size()) {
        int src = edges[i].src;
        int dest = edges[i].dest;

        // Check if adding the current edge forms a cycle
        if (!connected(src, dest, id)) {
            MST.push_back(edges[i]);
            unionSet(src, dest, id);
            count++;
        }
        
        i++;
    }

    return MST;
}

// Function to display the edges of the MST
void displayMST(const vector<Edge>& MST) {
    cout<<"Minimum Spanning Tree Edges:"<<endl<<endl;
    
    cout<<"Edge : Weight "<<endl;
    for (const auto& edge : MST) {
        cout<<edge.src<<" -- "<<edge.dest<<" : "<<edge.weight<<endl;
    }
}

int main() {
    int V = 6; // number of vertices in the graph
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 2},
        {2, 3, 4},
        {3, 4, 2}
    };

    vector<Edge> MST = kruskalMST(edges, V);

    displayMST(MST);

    return 0;
}

Output

Minimum Spanning Tree Edges:

Edge : Weight 
1 -- 2 : 1
1 -- 3 : 2
3 -- 4 : 2
0 -- 2 : 3

Time complexity can be reduced to: O((E + V) log(V)), where E is the number of edges, and V is the number of vertices, if we use Weighted Quick Union Implementation as explained here. This is because the time to sort edges is O(E log E) and Set Union and Find operations (O (log V)) are performed |V| times. Since G is a connected graph, we have |E| >= |V| – 1. Hence, we get the time complexity of Kruskal’s Algorithm as O(E log E).
Further, in a dense graph where E is close to V^2, the time complexity can be simplified to O(E log V).