Kruskal’s Algorithm

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. Unlike Prim’s algorithm, which builds the MST starting from a single vertex, Kruskal’s algorithm constructs the MST by sorting all edges by weight and then adding them one by one in increasing order of weight, provided they don’t form a cycle. This approach is especially useful when working with sparse graphs.

Ref: Kruskal’s Algorithm

How Kruskal’s Algorithm Works

  1. Sort All Edges: First, all edges of the graph are sorted in ascending order of their weights.
  2. Add Edges Without Forming Cycles: Starting from the smallest edge, each edge is added to the MST only if it doesn’t form a cycle. This is typically managed using the Union-Find (Disjoint Set Union, or DSU) data structure.
  3. Repeat Until MST is Formed: The process continues until the MST contains exactly V−1 edges, where V is the number of vertices.

Example Program: Kruskal’s Algorithm in C++

Here’s a C++ program implementing Kruskal’s algorithm. This program uses the Union-Find data structure to manage cycles efficiently.

Github code

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

using namespace std;

// Structure to represent an edge with its source, destination, and weight
struct Edge {
    int src, dest, weight;
};

// Comparator function to sort edges by weight in ascending order
bool compareEdge(Edge a, Edge b) {
    return a.weight < b.weight;
}

// Structure to represent a disjoint set for Union-Find
struct DisjointSet {
    vector<int> parent, rank;

    // Initialize disjoint set with n elements
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // Find the root of the set containing element x with path compression
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // Union of two sets 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]++;
            }
        }
    }
};

// Function to find the MST using Kruskal's algorithm
vector<Edge> kruskalMST(vector<Edge>& edges, int V) {
    // Sort edges by weight
    sort(edges.begin(), edges.end(), compareEdge);

    DisjointSet ds(V);
    vector<Edge> mst;

    for (const auto& edge : edges) {
        int u = edge.src;
        int v = edge.dest;

        // Check if the current edge forms a cycle
        if (ds.find(u) != ds.find(v)) {
            mst.push_back(edge);  // Include the edge in the MST
            ds.unionSets(u, v);   // Union the sets of u and v
        }

        // Stop if we've added enough edges for an MST
        if (mst.size() == V - 1) {
            break;
        }
    }
    return mst;
}

// Function to print the MST
void printMST(const vector<Edge>& mst) {
    cout << "Edges in the Minimum Spanning Tree:\n";
    for (const auto& edge : mst) {
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
    }
}

int main() {
    int V = 4;  // Number of vertices
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    // Find MST using Kruskal's algorithm
    vector<Edge> mst = kruskalMST(edges, V);

    // Print the MST
    printMST(mst);

    return 0;
}

Explanation of Code

  1. Edge Structure:
    • Defines an edge by its source vertex, destination vertex, and weight.
  2. Disjoint Set (Union-Find):
    • find: Finds the root of a vertex with path compression to flatten the tree structure.
    • unionSets: Unites two sets by rank to keep the tree balanced, reducing time complexity.
  3. Kruskal’s Algorithm:
    • Sorts all edges by weight.
    • Uses Union-Find to add the smallest edge to the MST that doesn’t form a cycle.
    • Stops when V−1V-1V−1 edges are added to the MST.
  4. Print Function:
    • printMST function displays each edge in the MST along with its weight.

Example Output

For the provided graph:

plaintextCopy codeEdges in the Minimum Spanning Tree:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Explanation of Output

The output shows the edges included in the MST, along with their weights, in ascending order of their addition.

Complexity Analysis

  • Time Complexity: O(ElogE+ElogV), where E is the number of edges and V is the number of vertices.
    • O(ElogE) is due to sorting the edges.
    • O(ElogV) is for performing union and find operations with path compression.
  • Space Complexity: O(E+V) for storing the edges and the disjoint set.

Kruskal’s algorithm is especially efficient for sparse graphs, where it operates faster than Prim’s algorithm. It is widely used in network design, clustering, and constructing minimum-cost spanning trees in various real-world applications.

Scroll to Top