C++ • GREEDY ALGORITHM Kruskal's Algorithm (Minimum Spanning Tree)

C++ • GREEDY ALGORITHM

Kruskal's Algorithm (Minimum Spanning Tree)

ALGORITHM

Kruskal's MST

TIME COMPLEXITY

O(E log E)

SPACE COMPLEXITY

O(V + E)

STRATEGY

Greedy / DSU

C++ Implementation

kruskal_mst.cpp

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

// Structure to represent a weighted edge
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class KruskalMST
{
    int V, E;
    vector<Edge> edges;
    vector<int> parent;
    vector<int> rank;

    // Find set of vertex i (with path compression)
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

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

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

public:

    // Constructor
    KruskalMST() {
        V = 0;
        E = 0;
    }

    // Input function
    void input() {
        cout << "Enter number of vertices: ";
        cin >> V;
        cout << "Enter number of edges: ";
        cin >> E;

        edges.resize(E);
        cout << "Enter edges (u v weight):\n";
        for (int i = 0; i < E; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        }
    }

    // Function to construct and print MST using Kruskal's algorithm
    void kruskalMST() {
        vector<Edge> result;
        int totalWeight = 0;

        // Sort all edges in non-decreasing order of their weight
        sort(edges.begin(), edges.end());

        parent.resize(V);
        rank.resize(V, 0);

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

        int e = 0; // An index variable, used for result[]
        int i = 0; // An index variable, used for sorted edges

        // Number of edges to be taken is equal to V-1
        while (e < V - 1 && i < E) {
            Edge next_edge = edges[i++];

            int x = find(next_edge.u);
            int y = find(next_edge.v);

            // If including this edge does't cause a cycle, include it
            // in result and increment the index of result for next edge
            if (x != y) {
                result.push_back(next_edge);
                totalWeight += next_edge.weight;
                unionSets(x, y);
                e++;
            }
        }

        // Print the constructed MST
        cout << "Edge \tWeight\n";
        for (const auto& edge : result) {
            cout << edge.u << " - " << edge.v << " \t" << edge.weight << "\n";
        }
        cout << "Total Weight of MST: " << totalWeight << endl;
    }
};

int main() {
    KruskalMST obj;

    obj.input();
    obj.kruskalMST();

    return 0;
}

Sample Input

Enter number of vertices: 4
Enter number of edges: 5
Enter edges (u v weight):
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Output

Edge 	Weight
2 - 3 	4 
0 - 3 	5 
0 - 1 	10 
Total Weight of MST: 19

Line-by-Line Explanation

Code

Meaning

struct Edge { u, v, weight; }

Defines a structure to hold the source, destination, and weight of each edge.

bool operator<(const Edge& ...)

Overloads the less-than operator to sort edges in ascending order of weight.

class KruskalMST

Creates a class named KruskalMST to encapsulate the Disjoint Set Union (DSU) and MST logic.

int find(int i)

Finds the representative/root of the set containing vertex i with path compression.

void unionSets(int x, int y)

Merges two disjoint sets containing x and y using union by rank.

KruskalMST()

Class constructor that initializes vertex and edge counts to zero.

void input()

Reads the number of vertices, edges, and edge details from the user.

sort(edges.begin(), edges.end());

Sorts all graph edges in non-decreasing order of weight.

if (x != y) { unionSets(x, y); }

Checks if adding the edge forms a cycle; if not, includes it in the MST.

KruskalMST obj;

Instantiates the KruskalMST object and triggers the constructor.

return 0;

Signals successful program execution.

How Kruskal's Algorithm works: Kruskal's algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST). It sorts all the edges from lowest weight to highest, then iterates through them and adds an edge to the MST only if the edge doesn't form a cycle (checked using a Disjoint Set Union / Union-Find data structure) until there are V - 1 edges in the tree.