Kruskal's Algorithm

Kruskal’s algorithm builds a minimum spanning tree by considering edges from cheapest to most expensive.

It uses Union-Find to avoid creating cycles.

Core Idea

Sort all edges by weight. For each edge, add it if it connects two different components. Skip it if both endpoints are already connected.

The greedy choice is safe because the cheapest edge connecting separate components can be part of a minimum spanning tree.

Function Contract

kruskal(vertex_count, edges) expects vertices numbered from 0 through vertex_count - 1 and edges as (weight, a, b) triples for an undirected graph.

It returns (total, chosen), where total is the MST edge-weight sum and chosen is the list of selected edges. If the graph is disconnected, chosen will contain fewer than vertex_count - 1 edges.

Python Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
 
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
 
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True
 
 
def kruskal(vertex_count, edges):
    union_find = UnionFind(vertex_count)
    total = 0
    chosen = []
 
    for weight, a, b in sorted(edges):
        if union_find.union(a, b):
            total += weight
            chosen.append((a, b, weight))
            if len(chosen) == vertex_count - 1:
                break
 
    return total, chosen

The union method returns True only when the edge connects two previously separate components.

Step-by-Step Idea

Sort edges by cost. The algorithm asks one question for each edge:

Does this edge connect two components that are currently separate?

If yes, add it. If no, it would create a cycle, so skip it.

Union-Find answers that question efficiently.

Why It Works

Kruskal’s algorithm is greedy. At each step, it chooses the cheapest edge that does not break the tree structure. The cut property behind MSTs says that the cheapest edge crossing a cut between components is safe to add.

The algorithm stops after choosing V - 1 edges because a spanning tree on V vertices has exactly V - 1 edges.

Complexity

Sorting edges costs O(E log E). Union-Find operations are near constant amortized time, so sorting usually dominates.

Failure Example

If the graph is disconnected, Kruskal still chooses safe edges inside each component, but it cannot choose V - 1 edges that connect all vertices.

That result is a minimum spanning forest, not a complete minimum spanning tree.

Common Confusions

Kruskal is edge-centered. It does not grow from one start vertex.

Sorting dominates much of the cost. The algorithm needs all candidate edges available or at least processable in weight order.

Another common mistake is adding the cheapest edge even when its endpoints are already connected. That creates a cycle and does not help connect new vertices.

When To Use It

Use Kruskal when edges are easy to sort, the graph may be sparse, and Union-Find is a natural way to track connected components.

Do not use Kruskal if the problem asks for shortest paths rather than cheapest full connection.

The Main Point

Kruskal builds an MST by scanning edges from cheapest to most expensive and using Union-Find to avoid cycles.