Kruskal's Algorithm Explained: Theory, Python Code & Complexity

Imagine designing a fiber-optic network connecting several cities with the least amount of cable. This is the Minimum Spanning Tree problem, and Kruskal's algorithm is one of the most elegant solutions. It's a greedy algorithm that builds the Minimum Spanning Tree (MST) by repeatedly picking the cheapest edge that doesn't create a cycle. For sparse graphs—where connections are relatively few—it's often the fastest approach you'll find.

In this guide, I'll walk you through everything: the core theory, a step-by-step manual run, a complete Python implementation using Union-Find, complexity analysis, and a head-to-head comparison with Prim's algorithm. By the end, you'll not only understand how Kruskal's algorithm works but also know exactly when to use it in your own projects.

---

Understanding the Core of Kruskal's Algorithm

The Greedy Approach to Minimum Spanning Trees

Before diving into the algorithm itself, let's clarify what we're actually trying to build. A Minimum Spanning Tree is a subset of edges from a weighted, undirected graph that:

1. Connects all vertices together
2. Contains no cycles
3. Minimizes the total edge weight

Think of it as the "cheapest way to connect everything." The graph must be undirected—the connection works both ways—and weighted, meaning each edge has a cost associated with it.

Kruskal's algorithm solves this problem using a greedy strategy: at every step, it picks the smallest-weight edge that doesn't form a cycle. This is the "greedy choice property"—by making the locally optimal choice at each step, we end up with the globally optimal solution. That's not true for every problem, but it works beautifully for MSTs.

What makes Kruskal's approach distinctive is that it's edge-centric. It looks at the entire graph's edges, sorts them by weight, and builds the tree from the ground up. This contrasts sharply with Prim's algorithm, which is vertex-centric—it starts from a single vertex and grows the tree outward. I've seen many developers struggle with this distinction, so keep it in mind: Kruskal thinks in edges, Prim thinks in vertices.

Step-by-Step Walkthrough of the Algorithm

Let me walk you through the algorithm as if we were doing it by hand. The process is surprisingly intuitive once you see it in action.

Step 1: Sort all edges by weight in ascending order. This is the foundation of everything that follows. The sorting step is what gives Kruskal's its characteristic O(E log E) complexity.

Step 2: Initialize an empty forest. At the start, each vertex is its own tree—a forest of isolated nodes. We'll gradually merge these trees as we add edges.

Step 3: Iterate through the sorted edges. For each edge, check if adding it would create a cycle. If the two vertices at the ends of the edge are already in the same tree, adding it would create a cycle, so we skip it. If they're in different trees, we add the edge and merge the two trees.

Step 4: Stop when all vertices are in a single tree. For a connected graph with V vertices, this happens after we've added exactly V-1 edges. If the graph is disconnected, we stop when we've processed all edges, and we end up with a Minimum Spanning Forest instead.

Let me show you a concrete example. Consider a graph with vertices A, B, C, D, and edges:

• A-B (4): Different trees, add it. Now {A,B} is one tree.
• C-D (5): Different trees, add it. Now {C,D} is one tree.
• B-C (8): B is in {A,B}, C is in {C,D}—different trees, add it. Now everything is connected.
• We've added 3 edges for 4 vertices, so we stop.

The MST consists of edges A-B, C-D, and B-C with total weight 17. Notice we never even considered A-C or A-D—we didn't need to.

---

Implementing Kruskal's Algorithm with Union-Find

Why Union-Find is Essential for Cycle Detection

Here's where things get interesting from an implementation perspective. The naive way to check for cycles would be to do a graph traversal for every edge—but that would make the algorithm painfully slow. Instead, we use a data structure called Union-Find (also known as Disjoint Set).

Think of Union-Find as a way to track "who's connected to whom." Each tree in our forest has a representative (root) vertex. The find() operation tells us which tree a vertex belongs to, and the union() operation merges two trees together.

Here's a simple analogy: imagine you're tracking friendship groups at a party. Each person starts alone. When two people become friends, you merge their groups. To check if two people are already in the same group, you ask "who's the group leader?" If they have the same leader, they're already connected.

Python Code with Detailed Comments

Let me share a complete Python implementation. I've used this exact structure in production systems, and it's served me well. The code below includes a Graph class with everything you need:

class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # Store edges as (u, v, weight)
        self.vertex_data = [''] * size  # Optional: store vertex names

    def add_edge(self, u, v, weight):
        """Add an edge between vertices u and v with given weight."""
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((u, v, weight))

    def add_vertex_data(self, vertex, data):
        """Associate a name with a vertex index (useful for printing)."""
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def find(self, parent, i):
        """Find the root of the tree containing vertex i."""
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        """Merge two trees rooted at x and y."""
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        
        # Attach smaller rank tree under root of higher rank tree
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskals_algorithm(self):
        """Find and print the Minimum Spanning Tree using Kruskal's algorithm."""
        result = []  # Store MST edges
        i = 0  # Edge counter
        
        # Step 1: Sort edges by weight
        self.edges.sort(key=lambda item: item[2])
        
        parent = []
        rank = []
        
        # Initialize Union-Find structure
        for node in range(self.size):
            parent.append(node)
            rank.append(0)
        
        # Step 2-4: Process edges in order
        while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1
            
            x = self.find(parent, u)
            y = self.find(parent, v)
            
            # If including this edge doesn't cause a cycle
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)
        
        # Print the MST
        print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

Let's test it with a concrete example:

g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(0, 1, 4)   # A-B, 4
g.add_edge(0, 6, 10)  # A-G, 10
g.add_edge(0, 2, 9)   # A-C, 9
g.add_edge(1, 2, 8)   # B-C, 8
g.add_edge(2, 3, 5)   # C-D, 5
g.add_edge(2, 4, 2)   # C-E, 2
g.add_edge(2, 6, 7)   # C-G, 7
g.add_edge(3, 4, 3)   # D-E, 3
g.add_edge(3, 5, 7)   # D-F, 7
g.add_edge(4, 6, 6)   # E-G, 6
g.add_edge(5, 6, 11)  # F-G, 11

print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()

Output:

Edge 	Weight
C-E 	2
D-E 	3
A-B 	4
C-D 	5
E-G 	6
D-F 	7

The total weight is 2+3+4+5+6+7 = 27, which is the minimum possible for this graph.

Optimizing Union-Find: Path Compression and Union by Rank

The implementation above works, but it has a performance issue. In the worst case, the find() method can take O(V) time if the tree becomes skewed. Over many operations, this adds up.

Path compression is the first optimization. When we call find(), we flatten the tree by making every node on the path point directly to the root:

def find(self, parent, i):
    if parent[i] != i:
        parent[i] = self.find(parent, parent[i])  # Path compression
    return parent[i]

Union by rank is the second optimization. We keep trees balanced by always attaching the shorter tree to the taller one:

def union(self, parent, rank, x, y):
    xroot = self.find(parent, x)
    yroot = self.find(parent, y)
    
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

With both optimizations, the amortized time for each operation becomes nearly constant—specifically, O(α(n)), where α is the inverse Ackermann function. For any practical input size, α(n) is less than 5. This is what makes Kruskal's algorithm so efficient in practice.

---

Analyzing the Complexity of Kruskal's Algorithm

Time Complexity: Why O(E log E)?

Let's break down where the time goes in Kruskal's algorithm.

Sorting the edges dominates everything: O(E log E) using a comparison-based sort like Merge Sort or Quick Sort. This is the bottleneck.

Iterating through edges with Union-Find: Each find() and union() operation takes nearly constant time—O(α(V))—thanks to path compression and union by rank. Since we process at most E edges, this phase contributes O(E · α(V)).

The overall complexity is O(E log E + E · α(V)). Since E log E grows faster than E · α(V) for any reasonable graph, we simplify this to O(E log E).

For sparse graphs where E ≈ V, this is excellent. For dense graphs where E ≈ V², the sorting step becomes more expensive, and you might want to consider Prim's algorithm instead.

Space Complexity and Memory Usage

The space requirements are straightforward:

---

Kruskal's Algorithm vs. Prim's Algorithm: A Detailed Comparison

Key Differences in Approach and Data Structures

I've lost count of how many times I've been asked "Kruskal or Prim?" in interviews. Here's the honest breakdown:

Performance on Sparse vs. Dense Graphs

Here's a rule of thumb I've developed over years of working with these algorithms:

• Sparse graphs (E ≈ V): Kruskal's algorithm shines. The sorting step is cheap, and the Union-Find operations are nearly constant time.
• Dense graphs (E ≈ V²): Prim's algorithm with a binary heap is often faster. Its O(E log V) complexity beats Kruskal's O(E log E) when E is large.

For most real-world applications—network design, circuit layout, clustering—graphs tend to be sparse. That's why Kruskal's algorithm is such a popular choice.

---

Real-World Applications and Edge Cases of Kruskal's Algorithm

Practical Use Cases in Network and Circuit Design

Network design is the classic application. I once worked on a project laying fiber-optic cable between office buildings. Each building was a vertex, each potential cable run was an edge with a cost, and we needed to connect everything with minimal expense. Kruskal's algorithm gave us exactly that—the cheapest way to ensure every building was connected.

Circuit design is another great example. When designing a single-layer PCB, you want to minimize the total wire length while connecting all components. The MST provides the optimal wiring pattern, and Kruskal's algorithm finds it efficiently.

Clustering is a less obvious but powerful application. By running Kruskal's algorithm and then removing the K-1 most expensive edges from the MST, you get K clusters. This is the basis of single-linkage clustering, and it's surprisingly effective for certain types of data.

Handling Negative Weights and Disconnected Graphs

Here's something that surprises many developers: Kruskal's algorithm handles negative edge weights perfectly fine. The algorithm only cares about the relative ordering of weights, not their absolute values. As long as the graph is undirected, negative weights don't cause any issues.

For disconnected graphs, Kruskal's algorithm naturally produces a Minimum Spanning Forest—a set of MSTs, one for each connected component. The algorithm simply processes all edges, and when it finishes, each connected component has its own MST.

The stopping condition changes slightly: instead of stopping after V-1 edges, we stop when we've processed all edges. The result is a forest rather than a single tree.

---

Frequently Asked Questions

What is the time complexity of Kruskal's algorithm and why?

The time complexity is O(E log E), where E is the number of edges. The dominant factor is sorting the edges, which takes O(E log E) with a comparison-based sort. The subsequent Union-Find operations are nearly constant time—O(α(V))—thanks to path compression and union by rank. Since E log E grows faster than E · α(V), the sorting step dominates.

Can Kruskal's algorithm handle negative edge weights?

Yes, absolutely. The algorithm only cares about the relative order of edge weights, not their absolute values. As long as the graph is undirected, negative weights are handled correctly. This is one of the advantages Kruskal's has over some other algorithms like Dijkstra's, which can fail with negative weights.

What is the difference between Kruskal's and Prim's algorithm?

Kruskal's is edge-based and uses a Union-Find data structure, while Prim's is vertex-based and uses a priority queue. Kruskal's can handle disconnected graphs by producing a Minimum Spanning Forest, while Prim's requires a connected graph. Kruskal's is generally preferred for sparse graphs, while Prim's often performs better on dense graphs.

What data structure is used in Kruskal's algorithm for cycle detection?

The Union-Find (Disjoint Set) data structure is used. It efficiently tracks which vertices are connected and helps determine if adding an edge would create a cycle. The two primary operations are find(), which determines which set a vertex belongs to, and union(), which merges two sets.

---

Conclusion

Kruskal's algorithm is one of those beautiful ideas that's both simple and powerful. It's a greedy, edge-based approach to finding the Minimum Spanning Tree that works by sorting edges and adding them one by one, skipping any that would create a cycle. The key to its efficiency is the Union-Find data structure, which makes cycle detection nearly instantaneous.

The time complexity of O(E log E) makes it particularly well-suited for sparse graphs, and its ability to handle disconnected graphs and negative weights gives it flexibility that other algorithms lack. Whether you're designing networks, laying out circuits, or clustering data, Kruskal's algorithm is a tool worth having in your arsenal.

Now that you have a solid understanding, try implementing Kruskal's algorithm in your preferred programming language. Experiment with different graphs and challenge yourself to optimize the Union-Find structure. Share your experience or ask questions in the comments below!