Course contentsShow
← Computer Science
Lesson 1016 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Kruskal's Algorithm: Implementation and Analysis

Implement Kruskal's algorithm and analyze its O(E log E) time complexity with union-find optimizations.

Kruskal's Algorithm: Implementation and Analysis

You'll learn how to implement Kruskal's algorithm efficiently and understand why its runtime is O(E log E).

Now that you've learned the conceptual overview and the union-find data structure, let's put them together into working code and analyze the performance.

Implementation Steps

Kruskal's algorithm sorts all edges by weight, then greedily adds edges that don't create cycles:

def kruskal_mst(n, edges):
    # edges is a list of (weight, u, v) tuples
    
    # Step 1: Sort edges by weight - O(E log E)
    edges.sort()
    
    # Step 2: Initialize union-find - O(V)
    parent = list(range(n))
    rank = [0] * n
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]
    
    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return False
        # Union by rank
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
        return True
    
    # Step 3: Process edges - O(E * α(V))
    mst = []
    for weight, u, v in edges:
        if union(u, v):  # No cycle created
            mst.append((weight, u, v))
    
    return mst

Time Complexity Analysis

  • Sorting edges: O(E log E) dominates
  • Union-find operations: E operations × α(V) ≈ O(E) where α is the inverse Ackermann function (practically constant)
  • Total: O(E log E) or equivalently O(E log V), since E ≤ V²

The union-find optimizations (path compression + union by rank) make cycle detection nearly free compared to sorting!

Key Takeaway: Kruskal's algorithm runs in O(E log E) time, dominated by sorting edges, with union-find providing near-constant-time cycle detection through path compression and union by rank optimizations.