What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) of a connected, undirected graph is a subgraph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

How does Kruskal's algorithm work?

Kruskal's algorithm is a greedy algorithm that finds an MST. It works by sorting all the edges in non-decreasing order of their weight. Then, it iterates through the sorted edges and adds an edge to the MST if adding it does not form a cycle.

Data Structures & Algorithms

Kruskal's Algorithm

Master Kruskal's algorithm for finding the Minimum Spanning Tree (MST) in your coding interviews. Our guide covers the greedy approach, Union-Find data structure, and offers AI-powered practice.

Kruskal's Algorithm Implementation

Here is a Python implementation of Kruskal's algorithm. It uses the Union-Find data structure to efficiently detect cycles.


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            return True
        return False

def kruskal(graph, num_vertices):
    # graph is a list of edges in the format (u, v, w)
    graph.sort(key=lambda item: item[2])
    dsu = DSU(num_vertices)
    mst = []
    total_weight = 0

    for u, v, w in graph:
        if dsu.union(u, v):
            mst.append((u, v, w))
            total_weight += w

    return mst, total_weight

AI Coach Tip: Kruskal's algorithm's efficiency heavily relies on the Union-Find data structure with path compression and union by rank/size optimizations. The time complexity is dominated by sorting the edges, making it O(E log E), where E is the number of edges. This is often better than Prim's algorithm for sparse graphs.