Kruskal's Algorithm

Introduction

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph. It works by sorting all edges by weight and adding the smallest edge to the MST, ensuring no cycles are formed using the Union-Find (Disjoint Set) approach.

In Kruskal's Algorithm, keep two things in mind:

Sort all edges by weight in ascending order.
Connect two nodes only if they aren't already connected by any path (Using DSU).

How Kruskal's Algorithm Works?

Sort all edges in ascending order based on weight.

Use a sorting algorithm to arrange edges from the smallest to the largest weight.

Process each edge in sorted order.

Connect the edges if they aren't already connected by any path.

Repeat until all edges are processed.

Continue adding edges to the MST until it contains V-1 edges, where V is the number of vertices in the graph.

Return the MST or its total weight.

The final MST will contain the minimum weight edges that connect all vertices without forming cycles.

Implementation

//kruskal'salgorithm.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}

void Union(int x, int y, vector<int> &parent, vector<int> &rank)
{
int x_parent = find(x, parent);
int y_parent = find(y, parent);
if (x_parent == y_parent)
    return;

if (rank[x_parent] > rank[y_parent])
{
    parent[y_parent] = x_parent;
}
else if (rank[x_parent] < rank[y_parent])
{
    parent[x_parent] = y_parent;
}
else
{
    parent[x_parent] = y_parent;
    rank[y_parent]++;
}
}

vector<vector<int>> spanningTree(vector<vector<pair<int, int>>> &adjlist)
{
vector<vector<int>> adj;
for (int u = 0; u < adjlist.size(); u++)
{
    for (auto &neigh : adjlist[u])
    {
        int v = neigh.first;
        int wt = neigh.second;
        adj.push_back({u, v, wt});
    }
}
sort(adj.begin(), adj.end(), [](vector<int> &a, vector<int> &b)
     { return a[2] < b[2]; });

return adj;
}
int kruskal(vector<vector<pair<int, int>>> &adjlist)
{
spanningTree(adjlist);
vector<vector<int>> adj = spanningTree(adjlist);
vector<int> parent(adj.size());
vector<int> rank(adj.size(), 0);
for (int i = 0; i < adj.size(); i++)
{
    parent[i] = i;
}
int sum = 0;
for (auto &temp : adj)
{
    int u = temp[0], v = temp[1], wt = temp[2];
    if (find(u, parent) != find(v, parent))
    {
        Union(u, v, parent, rank);
        sum += wt;
    }
}
return sum;
}
int main()
{
///             0----20-----3-----1-----4
///             |           |           | \      
///             5           5           2  4
///             |           |           |   \       
///             1-----1-----2           5--2--6
vector<vector<pair<int, int>>> adjlist(7);
adjlist[0].push_back({3, 20});
adjlist[0].push_back({1, 5});
adjlist[1].push_back({0, 5});
adjlist[1].push_back({2, 1});
adjlist[2].push_back({1, 1});
adjlist[2].push_back({3, 5});
adjlist[3].push_back({0, 20});
adjlist[3].push_back({2, 5});
adjlist[3].push_back({4, 1});
adjlist[4].push_back({3, 1});
adjlist[4].push_back({5, 2});
adjlist[4].push_back({6, 4});
adjlist[5].push_back({4, 2});
adjlist[5].push_back({6, 2});
adjlist[6].push_back({5, 2});
adjlist[6].push_back({4, 4});
cout<<kruskal(adjlist);
}

# kruskals_algorithm.py

class UnionFind:
 def __init__(self, n):
     self.parent = list(range(n))
     self.rank = [0] * n
 
 def find(self, x):
     if self.parent[x] != x:
         self.parent[x] = self.find(self.parent[x])  # Path compression
     return self.parent[x]
 
 def union(self, x, y):
     root_x = self.find(x)
     root_y = self.find(y)
     
     if root_x != root_y:
         # Union by rank
         if self.rank[root_x] < self.rank[root_y]:
             self.parent[root_x] = root_y
         elif self.rank[root_x] > self.rank[root_y]:
             self.parent[root_y] = root_x
         else:
             self.parent[root_y] = root_x
             self.rank[root_x] += 1
         return True
     return False

def kruskals_algorithm(num_vertices, edges):
 """
 Kruskal's algorithm to find Minimum Spanning Tree (MST)
 
 Args:
     num_vertices: Number of vertices in the graph
     edges: List of tuples (u, v, weight) representing edges
 
 Returns:
     Tuple of (mst_weight, mst_edges)
 """
 # Sort edges by weight
 edges.sort(key=lambda x: x[2])
 
 uf = UnionFind(num_vertices)
 mst_weight = 0
 mst_edges = []
 
 for u, v, weight in edges:
     if uf.union(u, v):
         mst_weight += weight
         mst_edges.append((u, v, weight))
         
         # MST has exactly (V-1) edges
         if len(mst_edges) == num_vertices - 1:
             break
 
 return mst_weight, mst_edges

# Example usage
if __name__ == "__main__":
 # Example graph with 7 vertices
 num_vertices = 7
 edges = [
     (0, 3, 20), (0, 1, 5), (1, 2, 1), (2, 3, 5),
     (3, 4, 1), (4, 5, 2), (4, 6, 4), (5, 6, 2)
 ]
 
 mst_weight, mst_edges = kruskals_algorithm(num_vertices, edges)
 
 print(f"Minimum Spanning Tree Weight: {mst_weight}")
 print("MST Edges:")
 for u, v, weight in mst_edges:
     print(f"  {u} -- {v} : {weight}")

# Output: Minimum Spanning Tree Weight: 11

// kruskals_algorithm.js

class UnionFind {
 constructor(n) {
     this.parent = Array.from({length: n}, (_, i) => i);
     this.rank = new Array(n).fill(0);
 }
 
 find(x) {
     if (this.parent[x] !== x) {
         this.parent[x] = this.find(this.parent[x]); // Path compression
     }
     return this.parent[x];
 }
 
 union(x, y) {
     const rootX = this.find(x);
     const rootY = this.find(y);
     
     if (rootX !== rootY) {
         // Union by rank
         if (this.rank[rootX] < this.rank[rootY]) {
             this.parent[rootX] = rootY;
         } else if (this.rank[rootX] > this.rank[rootY]) {
             this.parent[rootY] = rootX;
         } else {
             this.parent[rootY] = rootX;
             this.rank[rootX]++;
         }
         return true;
     }
     return false;
 }
}

function kruskalsAlgorithm(numVertices, edges) {
 /**
  * Kruskal's algorithm to find Minimum Spanning Tree (MST)
  * 
  * @param {number} numVertices - Number of vertices in the graph
  * @param {Array} edges - Array of [u, v, weight] representing edges
  * @returns {Object} - {mstWeight, mstEdges}
  */
 // Sort edges by weight
 edges.sort((a, b) => a[2] - b[2]);
 
 const uf = new UnionFind(numVertices);
 let mstWeight = 0;
 const mstEdges = [];
 
 for (const [u, v, weight] of edges) {
     if (uf.union(u, v)) {
         mstWeight += weight;
         mstEdges.push([u, v, weight]);
         
         // MST has exactly (V-1) edges
         if (mstEdges.length === numVertices - 1) {
             break;
         }
     }
 }
 
 return { mstWeight, mstEdges };
}

// Example usage
function main() {
 // Example graph with 7 vertices
 const numVertices = 7;
 const edges = [
     [0, 3, 20], [0, 1, 5], [1, 2, 1], [2, 3, 5],
     [3, 4, 1], [4, 5, 2], [4, 6, 4], [5, 6, 2]
 ];
 
 const { mstWeight, mstEdges } = kruskalsAlgorithm(numVertices, edges);
 
 console.log(`Minimum Spanning Tree Weight: ${mstWeight}`);
 console.log("MST Edges:");
 for (const [u, v, weight] of mstEdges) {
     console.log(`  ${u} -- ${v} : ${weight}`);
 }
}

main();

// Output: Minimum Spanning Tree Weight: 11

Time Complexity

Building Edge list

The function spanningTree() converts the adjacency list to an edge list.
Iterating over adjlist takes O(V + E) time, where V is the number of vertices and E is the number of edges.
Storing the edges in a vector also takes O(E) time.

Sorting the Edge List

The edge list is sorted using sort(), which takes O(E log E) time.

Union-Find Operations (With Path Compression & Union by Rank)

We initialize parent and rank arrays in O(V) time.
Processing each edge requires O(α(V)) (Inverse Ackermann function) for find() and Union(), which is nearly O(1).
Since we process at most E edges, this step takes O(E α(V)).

Overall Time Complexity

O(E)+O( log E)+O(V)+O(E α (V))
The final time complexity is O(E log E).

Space Complexity

Stores edge list O(E).
Uses parent and rank arrays (DSU) O(V).
Space Complexity O(V+E).

Kruskal's Algorithm

On this page