Kruskal's Minimum Spanning Tree

Generated on 2025-07-10 01:58:00 Algorithm Cheatsheet for Technical Interviews

---

Kruskal’s Minimum Spanning Tree (MST) Cheatsheet

1. Quick Overview

What is it? Kruskal’s algorithm finds the Minimum Spanning Tree (MST) for a weighted, undirected graph. An MST connects all vertices with the minimum possible total edge weight, without forming cycles.

When to use it?

• When you need to connect all nodes in a graph with the least total cost (e.g., network design, clustering).
• When the graph is sparse (fewer edges compared to vertices). For dense graphs, Prim’s algorithm might be more efficient.

2. Time & Space Complexity

Metric	Big O Notation	Explanation
Time Complexity	O(E log E)	E = number of edges. Dominant operation is sorting the edges. Union-Find operations take nearly constant time (amortized).
Space Complexity	O(V)	V = number of vertices. Primarily due to the Union-Find data structure.

3. Implementation

Python:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n  # Used for path compression

    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:
            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  # Indicate a successful union
        return False  # Indicate a cycle

def kruskal(num_vertices, edges):
    """
    Finds the Minimum Spanning Tree (MST) using Kruskal's algorithm.

    Args:
        num_vertices: The number of vertices in the graph.
        edges: A list of tuples representing edges in the format (weight, u, v),
               where weight is the edge weight, u and v are the vertices connected by the edge.

    Returns:
        A list of tuples representing the edges in the MST, in the format (u, v, weight),
        or None if the graph is disconnected.
    """

    edges.sort()  # Sort edges by weight in ascending order
    mst = []
    uf = UnionFind(num_vertices)
    mst_weight = 0
    num_edges_added = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            mst_weight += weight
            num_edges_added += 1

    if num_edges_added != num_vertices - 1:
        return None  # Graph is disconnected
    return mst


# Example Usage
if __name__ == '__main__':
    num_vertices = 5
    edges = [
        (2, 0, 1),
        (3, 0, 2),
        (6, 1, 3),
        (8, 1, 2),
        (5, 2, 3),
        (9, 2, 4),
        (7, 3, 4)
    ]

    mst = kruskal(num_vertices, edges)

    if mst:
        print("Minimum Spanning Tree:")
        for u, v, weight in mst:
            print(f"Edge: ({u}, {v}) Weight: {weight}")
    else:
        print("Graph is disconnected, no MST exists.")

Java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(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]++;
            }
            return true; // Indicate a successful union
        }
        return false; // Indicate a cycle
    }
}

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}


public class Kruskal {

    public static List<Edge> kruskalMST(int numVertices, List<Edge> edges) {
        Collections.sort(edges); // Sort edges by weight
        List<Edge> mst = new ArrayList<>();
        UnionFind uf = new UnionFind(numVertices);
        int numEdgesAdded = 0;

        for (Edge edge : edges) {
            if (uf.union(edge.src, edge.dest)) {
                mst.add(edge);
                numEdgesAdded++;
            }
        }

        if (numEdgesAdded != numVertices - 1) {
            return null; // Graph is disconnected
        }
        return mst;
    }

    public static void main(String[] args) {
        int numVertices = 5;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(1, 3, 6));
        edges.add(new Edge(1, 2, 8));
        edges.add(new Edge(2, 3, 5));
        edges.add(new Edge(2, 4, 9));
        edges.add(new Edge(3, 4, 7));

        List<Edge> mst = kruskalMST(numVertices, edges);

        if (mst != null) {
            System.out.println("Minimum Spanning Tree:");
            for (Edge edge : mst) {
                System.out.println("Edge: (" + edge.src + ", " + edge.dest + ") Weight: " + edge.weight);
            }
        } else {
            System.out.println("Graph is disconnected, no MST exists.");
        }
    }
}

C++:

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

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Subset {
    int parent, rank;
};

int find(vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent); // Path compression
    return subsets[i].parent;
}

void Union(vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

vector<Edge> kruskalMST(int numVertices, vector<Edge>& edges) {
    vector<Edge> mst;
    sort(edges.begin(), edges.end(), compareEdges); // Sort edges by weight

    vector<Subset> subsets(numVertices);
    for (int v = 0; v < numVertices; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int numEdgesAdded = 0;
    for (const auto& edge : edges) {
        int srcRoot = find(subsets, edge.src);
        int destRoot = find(subsets, edge.dest);

        if (srcRoot != destRoot) {
            mst.push_back(edge);
            Union(subsets, srcRoot, destRoot);
            numEdgesAdded++;
        }
    }

    if (numEdgesAdded != numVertices - 1) {
        return {}; // Graph is disconnected
    }
    return mst;
}

int main() {
    int numVertices = 5;
    vector<Edge> edges = {
        {0, 1, 2},
        {0, 2, 3},
        {1, 3, 6},
        {1, 2, 8},
        {2, 3, 5},
        {2, 4, 9},
        {3, 4, 7}
    };

    vector<Edge> mst = kruskalMST(numVertices, edges);

    if (!mst.empty()) {
        cout << "Minimum Spanning Tree:" << endl;
        for (const auto& edge : mst) {
            cout << "Edge: (" << edge.src << ", " << edge.dest << ") Weight: " << edge.weight << endl;
        }
    } else {
        cout << "Graph is disconnected, no MST exists." << endl;
    }

    return 0;
}

4. Common Patterns

• Connecting components: Kruskal’s is used to connect disjoint sets of vertices into a single connected component with minimal cost.
• Clustering: MST can be used to identify clusters of data points where edges represent similarity (or distance) between points.
• Network design: Finding the cheapest way to connect all computers in a network.
• Image segmentation: Using pixel similarity as edge weights.

5. Pro Tips

• Union-Find Optimization: Path compression and union by rank greatly improve the performance of the Union-Find data structure, making its operations nearly constant time in practice (amortized).
• Edge Representation: Represent edges as tuples or objects containing source vertex, destination vertex, and weight.
• Disconnected Graphs: Check if the resulting MST contains V-1 edges. If not, the graph is disconnected, and no MST exists. Return None or an empty list in this case.
• Sorting: The sort() function is crucial and contributes significantly to the overall time complexity. Use an efficient sorting algorithm (e.g., mergesort, quicksort, or heapsort).

6. Practice Problems

• LeetCode 1135. Connecting Cities With Minimum Cost: Direct application of Kruskal’s to find the minimum cost to connect all cities.
• LeetCode 1584. Min Cost to Connect All Points: Convert the problem into a graph problem where points are vertices, and distances between points are edge weights. Then apply Kruskal’s.
• Codeforces 1245A - Good ol’ Numbers Coloring: (Slightly more advanced) Relates to the concept of connectedness and finding a spanning tree.

7. Templates

C++ Template:

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

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Subset {
    int parent, rank;
};

int find(vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

vector<Edge> kruskalMST(int numVertices, vector<Edge>& edges) {
    vector<Edge> mst;
    sort(edges.begin(), edges.end(), compareEdges);

    vector<Subset> subsets(numVertices);
    for (int v = 0; v < numVertices; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int numEdgesAdded = 0;
    for (const auto& edge : edges) {
        int srcRoot = find(subsets, edge.src);
        int destRoot = find(subsets, edge.dest);

        if (srcRoot != destRoot) {
            mst.push_back(edge);
            Union(subsets, srcRoot, destRoot);
            numEdgesAdded++;
        }
    }

    if (numEdgesAdded != numVertices - 1) {
        return {}; // Graph is disconnected
    }
    return mst;
}

int main() {
    // Input: numVertices, edges (vector of Edge structs)
    // Call kruskalMST(numVertices, edges) to get the MST
    // Handle disconnected graph case (empty MST vector)
    return 0;
}

Python Template:

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])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            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 kruskal(num_vertices, edges):
    edges.sort()
    mst = []
    uf = UnionFind(num_vertices)
    num_edges_added = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            num_edges_added += 1

    if num_edges_added != num_vertices - 1:
        return None  # Graph is disconnected
    return mst

if __name__ == '__main__':
    # Input: num_vertices, edges (list of (weight, u, v) tuples)
    # Call mst = kruskal(num_vertices, edges)
    # Handle disconnected graph case (mst is None)
    pass

Java Template:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(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]++;
            }
            return true;
        }
        return false;
    }
}

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class KruskalTemplate {

    public static List<Edge> kruskalMST(int numVertices, List<Edge> edges) {
        Collections.sort(edges);
        List<Edge> mst = new ArrayList<>();
        UnionFind uf = new UnionFind(numVertices);
        int numEdgesAdded = 0;

        for (Edge edge : edges) {
            if (uf.union(edge.src, edge.dest)) {
                mst.add(edge);
                numEdgesAdded++;
            }
        }

        if (numEdgesAdded != numVertices - 1) {
            return null; // Graph is disconnected
        }
        return mst;
    }

    public static void main(String[] args) {
        // Input: numVertices, edges (List of Edge objects)
        // Call kruskalMST(numVertices, edges) to get the MST
        // Handle disconnected graph case (null MST)
    }
}