C++ Program to Find the Minimum Spanning Tree Using Kruskal's Algorithm

Table of Contents

Introduction

The Minimum Spanning Tree (MST) is a fundamental problem in computer science, often found in network design, clustering, and various optimization tasks. Kruskal’s Algorithm is a popular algorithm used to find the MST of a connected, undirected graph. Named after Joseph Kruskal, this algorithm follows a greedy approach to connect all vertices in the graph while minimizing the total edge weight.

In this article, we will delve into the concept of the Minimum Spanning Tree, explain Kruskal’s Algorithm, and provide a comprehensive C++ program to implement it. We will walk through three examples to illustrate the solution and output clearly.

Prerequisites

Before diving into the implementation, it’s beneficial to have:

Basic understanding of algorithms: Knowledge of graph theory and greedy algorithms.
Familiarity with C++ programming: Proficiency in C++ syntax, data structures, and standard I/O.
Understanding of data structures: Particularly sets and graphs, which are central to Kruskal’s Algorithm.

Kruskal’s Algorithm

Definition and Formula

Kruskal’s Algorithm aims to find the MST by following these steps:

Sort all the edges in non-decreasing order of their weight.
Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If a cycle is not formed, include this edge. Else, discard it.
Repeat step 2 until there are V−1 edges in the spanning tree (where V is the number of vertices).

The algorithm uses the Union-Find data structure to manage and detect cycles efficiently.

Implementing Kruskal’s Algorithm in C++

1.1 Basic Implementation

Below is the basic implementation of Kruskal’s Algorithm in C++.

C++

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

using namespace std;

class Edge {
public:
    int src, dest, weight;
    Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};

class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int s, int d, int w) {
        edges.push_back(Edge(s, d, w));
    }

    int findSet(int i, vector<int>& parent) {
        if (i == parent[i])
            return i;
        else
            return parent[i] = findSet(parent[i], parent);
    }

    void unionSet(int u, int v, vector<int>& parent, vector<int>& rank) {
        int uroot = findSet(u, parent);
        int vroot = findSet(v, parent);
        if (rank[uroot] < rank[vroot])
            parent[uroot] = vroot;
        else if (rank[uroot] > rank[vroot])
            parent[vroot] = uroot;
        else {
            parent[vroot] = uroot;
            rank[uroot]++;
        }
    }

    void kruskalMST() {
        vector<Edge> result;
        sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
            return a.weight < b.weight;
        });

        vector<int> parent(V);
        vector<int> rank(V, 0);

        for (int i = 0; i < V; i++)
            parent[i] = i;

        for (Edge e : edges) {
            int u = findSet(e.src, parent);
            int v = findSet(e.dest, parent);

            if (u != v) {
                result.push_back(e);
                unionSet(u, v, parent, rank);
            }
        }

        cout << "Edges in the MST:" << endl;
        for (Edge e : result) {
            cout << e.src << " -- " << e.dest << " == " << e.weight << endl;
        }
    }
};

int main() {
    int V = 4;
    int E = 5;
    Graph g(V, E);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 6);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 3, 15);
    g.addEdge(2, 3, 4);

    g.kruskalMST();

    return 0;
}

1.2 Example Usage

The example above initializes a graph with 4 vertices and 5 edges, then finds the MST using Kruskal’s Algorithm.

1.3 Output for Example 1

C++

Edges in the MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Additional Examples

2.1 Example 2: Larger Graph

In this example, we will consider a larger graph with 5 vertices and 7 edges.

C++

int main() {
    int V = 5;
    int E = 7;
    Graph g(V, E);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 3, 6);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 3, 8);
    g.addEdge(1, 4, 5);
    g.addEdge(2, 4, 7);
    g.addEdge(3, 4, 9);

    g.kruskalMST();

    return 0;
}

Output for Example 2

C++

Edges in the MST:
0 -- 1 == 2
1 -- 2 == 3
1 -- 4 == 5
0 -- 3 == 6

2.2 Example 3: Sparse Graph

This example demonstrates a sparse graph with fewer edges.

C++

int main() {
    int V = 4;
    int E = 3;
    Graph g(V, E);
    g.addEdge(0, 1, 1);
    g.addEdge(1, 2, 2);
    g.addEdge(2, 3, 3);

    g.kruskalMST();

    return 0;
}

Output for Example 3

C++

Edges in the MST:
0 -- 1 == 1
1 -- 2 == 2
2 -- 3 == 3

Conclusion

Kruskal’s Algorithm is a powerful and efficient method for finding the Minimum Spanning Tree of a graph. By leveraging the Union-Find data structure, it effectively manages and detects cycles, ensuring an optimal solution. This article provided a detailed C++ implementation of Kruskal’s Algorithm, complete with examples and outputs to illustrate its practical application