Kruskal's Algorithm: Find Minimum Spanning Tree

Description

Kruskal's algorithm is a minimum spanning tree algorithm that finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

How It Works

Sort all edges in non-decreasing order of their weight
Initialize a forest where each vertex is a separate tree
For each edge in sorted order:
- If including the edge doesn't create a cycle:
  - Add it to the spanning tree
  - Union the sets of vertices it connects
Continue until spanning tree has (V-1) edges

Visualization

Speed:

Click Start to begin visualization

Implementation


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    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):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

class Kruskal:
    @staticmethod
    def minimum_spanning_tree(vertices: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
        """
        Find the minimum spanning tree using Kruskal's algorithm.
        
        Args:
            vertices: Number of vertices in the graph
            edges: List of edges as tuples (from_vertex, to_vertex, weight)
            
        Returns:
            List of edges in the minimum spanning tree
        """
        # Sort edges by weight
        edges = sorted(edges, key=lambda x: x[2])
        
        # Initialize Union-Find data structure
        uf = UnionFind(vertices)
        
        mst = []
        total_weight = 0
        
        # Process edges in ascending order of weight
        for u, v, weight in edges:
            if uf.union(u, v):
                mst.append((u, v, weight))
                total_weight += weight
                
                # Stop when we have V-1 edges
                if len(mst) == vertices - 1:
                    break
        
        return mst

# Example usage
if __name__ == "__main__":
    # Example graph
    V = 4
    edges = [
        (0, 1, 10),  # Edge from vertex 0 to 1 with weight 10
        (0, 2, 6),
        (0, 3, 5),
        (1, 3, 15),
        (2, 3, 4)
    ]
    
    mst = Kruskal.minimum_spanning_tree(V, edges)
    
    print("Minimum Spanning Tree edges:")
    total_weight = 0
    for u, v, weight in mst:
        print(f"Edge {u}-{v}: weight = {weight}")
        total_weight += weight
    print(f"Total MST weight: {total_weight}")


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

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    
public:
    UnionFind(int size) : parent(size), rank(size, 0) {
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }
    
    bool union_sets(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank[px] < rank[py]) {
            std::swap(px, py);
        }
        parent[py] = px;
        if (rank[px] == rank[py]) {
            rank[px]++;
        }
        return true;
    }
};

class Kruskal {
public:
    struct Edge {
        int from, to, weight;
        
        Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
        
        bool operator<(const Edge& other) const {
            return weight < other.weight;
        }
    };
    
    static std::vector<Edge> minimum_spanning_tree(int vertices, std::vector<Edge>& edges) {
        // Sort edges by weight
        std::sort(edges.begin(), edges.end());
        
        UnionFind uf(vertices);
        std::vector<Edge> mst;
        int total_weight = 0;
        
        for (const Edge& edge : edges) {
            if (uf.union_sets(edge.from, edge.to)) {
                mst.push_back(edge);
                total_weight += edge.weight;
                
                if (mst.size() == vertices - 1) {
                    break;
                }
            }
        }
        
        return mst;
    }
};

int main() {
    // Example graph
    int V = 4;
    std::vector<Kruskal::Edge> edges = {
        {0, 1, 10},  // Edge from vertex 0 to 1 with weight 10
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    
    auto mst = Kruskal::minimum_spanning_tree(V, edges);
    
    std::cout << "Minimum Spanning Tree edges:\n";
    int total_weight = 0;
    for (const auto& edge : mst) {
        std::cout << "Edge " << edge.from << "-" << edge.to 
                  << ": weight = " << edge.weight << "\n";
        total_weight += edge.weight;
    }
    std::cout << "Total MST weight: " << total_weight << "\n";
    
    return 0;
}


using System;
using System.Collections.Generic;
using System.Linq;

public class UnionFind
{
    private int[] parent;
    private int[] rank;
    
    public UnionFind(int size)
    {
        parent = Enumerable.Range(0, size).ToArray();
        rank = new int[size];
    }
    
    public int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]);  // Path compression
        }
        return parent[x];
    }
    
    public bool Union(int x, int y)
    {
        int px = Find(x), py = Find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank[px] < rank[py])
        {
            (px, py) = (py, px);
        }
        parent[py] = px;
        if (rank[px] == rank[py])
        {
            rank[px]++;
        }
        return true;
    }
}

public class Kruskal
{
    public record Edge(int From, int To, int Weight);
    
    public static List<Edge> MinimumSpanningTree(int vertices, List<Edge> edges)
    {
        // Sort edges by weight
        edges.Sort((a, b) => a.Weight.CompareTo(b.Weight));
        
        var uf = new UnionFind(vertices);
        var mst = new List<Edge>();
        int totalWeight = 0;
        
        foreach (var edge in edges)
        {
            if (uf.Union(edge.From, edge.To))
            {
                mst.Add(edge);
                totalWeight += edge.Weight;
                
                if (mst.Count == vertices - 1)
                {
                    break;
                }
            }
        }
        
        return mst;
    }
    
    public static void Main()
    {
        // Example graph
        int V = 4;
        var edges = new List<Edge>
        {
            new(0, 1, 10),  // Edge from vertex 0 to 1 with weight 10
            new(0, 2, 6),
            new(0, 3, 5),
            new(1, 3, 15),
            new(2, 3, 4)
        };
        
        var mst = MinimumSpanningTree(V, edges);
        
        Console.WriteLine("Minimum Spanning Tree edges:");
        int totalWeight = 0;
        foreach (var edge in mst)
        {
            Console.WriteLine($"Edge {edge.From}-{edge.To}: weight = {edge.Weight}");
            totalWeight += edge.Weight;
        }
        Console.WriteLine($"Total MST weight: {totalWeight}");
    }
}

Complexity Analysis

Time Complexity

O(E log E) where:

E is the number of edges
Sorting edges takes O(E log E)
Union-Find operations take O(α(V)), which is nearly constant

Space Complexity

O(V) where:

V is the number of vertices
Space needed for the disjoint-set data structure
Additional O(E) space for storing sorted edges

Advantages and Disadvantages

Advantages

Simple to implement
Works well with sparse graphs
Guarantees minimum spanning tree
Can be easily parallelized
Good for distributed systems

Disadvantages

Not as efficient for dense graphs
Requires sorting all edges
Requires Union-Find data structure
Not suitable for dynamic graphs
Memory intensive for large graphs

Applications

Network design (computer networks, transportation)
Circuit design in electronics
Water supply networks
Clustering algorithms
Approximation algorithms for NP-hard problems

Quick Info

Kruskal's Algorithm