Kruskal's Algorithm for MST with Union-Find

Welcome to our next lesson on Minimum Spanning Trees. In our previous session, we mastered Prim's algorithm, which finds an MST by growing a single tree from an arbitrary starting vertex. Today, we'll explore Kruskal's algorithm, a powerful alternative that takes a completely different, yet equally effective, greedy approach.

The learning outcome for this lesson is to implement Kruskal's algorithm for MST construction using Union-Find to detect cycles. This method elegantly combines sorting with the Disjoint Set Union (DSU) data structure you studied in Module 8. By the end of this lesson, you'll have a second robust tool for solving MST problems and a deeper appreciation for how different data structures can be combined to create efficient algorithms.

The Forest and the Trees: A New Greedy Strategy

While Prim's algorithm maintains a single connected component that grows to encompass the entire graph, Kruskal's algorithm starts with a "forest" of components and systematically merges them. Initially, every vertex is its own tiny tree in this forest. The algorithm then considers all edges in the graph, sorted by weight from smallest to largest. It adds an edge to our growing collection of MST edges only if it connects two previously disconnected components.

This strategy is also greedy and correct due to the Cut Property we discussed. By always picking the globally lightest available edge, we are ensuring that we are always picking a safe edge. The key challenge, then, is efficiently determining whether an edge connects two different components or if it's redundant (i.e., its endpoints are already connected), which would form a cycle.

This image visualizes the process. Edges are considered in increasing order of weight. The ones that connect new components are added (black), while those that would form a cycle are discarded as "obsolete" (gray).

The Key to Cycle Detection: Union-Find

How do we know if adding an edge (u, v) will form a cycle? It will form a cycle if and only if vertices u and v are already part of the same connected component. Answering the question "Are these two vertices already connected?" is precisely what the Union-Find (or Disjoint Set Union) data structure is designed for.

As you'll recall from Module 8, Union-Find allows us to:

1. Place each vertex in its own set.
2. Efficiently merge, or union, the sets of two vertices.
3. Efficiently check, or find, if two vertices belong to the same set by comparing their representatives (roots).

This gives us the core logic for Kruskal's algorithm:

For each edge (u, v) sorted by weight:
  if find(u) != find(v):
    // u and v are in different components, so adding this edge won't create a cycle.
    Add edge (u, v) to the MST.
    union(u, v) // Merge the two components.

To ensure this is fresh in your mind, and because it's so critical to this algorithm, let's do a quick but thorough review of the optimized Union-Find data structure.

The image below shows how the abstract parent and rank arrays from the Union-Find data structure correspond to the state of the graph as the MST is being constructed.

Walkthrough and Implementation

With the Union-Find mechanism fresh in your mind, let's see how all the pieces fit together in a complete implementation. The following video provides an excellent step-by-step walkthrough of the algorithm and then translates it into code.

To complement the video, let's study a practical implementation that solves a common interview-style problem. This will also show you a valuable pattern for modeling problems as graphs.

Complexity Analysis

Let's break down the performance of Kruskal's algorithm. Let $V$ be the number of vertices and $E$ be the number of edges.

• Time Complexity: $O(E\log E)$ or $O(E\log V)$

  • The first step is to create a list of all edges, which takes $O(E)$ time.
  • The most significant step is sorting these $E$ edges. This takes $O(E\log E)$ time.
  • Then, we iterate through each of the $E$ sorted edges. For each edge, we perform two find operations and at most one union operation.
  • With path compression and union by size/rank, these Union-Find operations have an amortized time complexity of $O(\alpha (V))$, which is nearly constant.
  • The total time is therefore dominated by the sorting step: $O(E\log E)$. Since for any connected graph, $E$ can be at most $V^2$, $\log E$ is in $O(\log V)$. So, the complexity is often stated as $O(E\log V)$ to allow for easier comparison with Prim's algorithm.

• Auxiliary Space Complexity: $O(V+E)$

  • We need $O(E)$ space to store the list of all edges for sorting.
  • The Union-Find data structure requires $O(V)$ space for its parent and size/rank arrays.
  • Therefore, the total auxiliary space is $O(V+E)$.

Conclusion

In this lesson, we have implemented Kruskal's algorithm, the second major approach to finding a Minimum Spanning Tree. You've seen how it leverages a different greedy strategy than Prim's and relies heavily on the Union-Find data structure for its efficiency.

Key Takeaways:

• Kruskal's algorithm works by sorting all graph edges by weight and iteratively adding the cheapest edge that does not form a cycle.
• It starts with a forest of $V$ components and merges them until a single spanning tree is formed.
• The Union-Find data structure is the ideal tool for cycle detection, using the find(u) != find(v) check to determine if an edge connects two disjoint components.
• The time complexity is dominated by the initial edge sort, resulting in $O(E\log E)$.
• Patterns like the "dummy node" can transform problems with vertex weights into standard graph problems solvable with MST algorithms.

In our next module, we will move on to a different class of graph problems involving directed graphs. You'll learn about Topological Sort, an algorithm for ordering vertices in a directed acyclic graph based on their dependencies, which is fundamental to problems like task scheduling and dependency resolution.