Kruskal's Algorithm and Union-Find for MSTs

1. The Greedy Strategy of Kruskal's Algorithm

Kruskal's algorithm is a classic example of a greedy algorithm. This means that at each step, it makes the choice that seems best at that moment, without considering the future consequences of that choice. For Kruskal's, the greedy choice is simple: always pick the available edge with the smallest weight.

The overall process is as follows:

1. Create a list of all edges in the graph and sort them in non-decreasing order of their weights.
2. Initialize a new graph, the MST, with all the vertices of the original graph but no edges.
3. Iterate through the sorted edges. For each edge (u, v):
   • Check if adding this edge to the MST would form a cycle.
   • If it does not form a cycle, add the edge to the MST.
   • If it does form a cycle, discard the edge and move to the next one.
4. The algorithm terminates when the MST has $V-1$ edges, where $V$ is the number of vertices.

To see this high-level process in action, let's watch a short introductory video.

This greedy approach of picking the "cheapest" edge at every step feels intuitive, but the crucial part is knowing how to efficiently detect whether adding an edge creates a cycle. This is where your knowledge from the previous lesson comes into play.

2. Detecting Cycles with Union-Find

As we just saw, the main challenge in Kruskal's algorithm is cycle detection. Trying to traverse the graph to check for a cycle after adding each edge would be very inefficient. Instead, we can use the Union-Find data structure to track the connected components of the growing MST.

Here’s how it works:

• Initialization: We begin by placing each vertex in its own set using the make_set() operation. This represents a forest of $V$ trees, each containing a single vertex.
• Iteration: As we process each edge (u, v) from our sorted list:
  1. We use find(u) and find(v) to determine the representatives (roots) of the sets containing u and v.
  2. If find(u) is the same as find(v), it means u and v are already in the same connected component. Adding the edge (u, v) would create a cycle. Therefore, we discard this edge.
  3. If find(u) is different from find(v), the vertices are in different components. Adding the edge (u, v) will not create a cycle. So, we add this edge to our MST and merge the two components by calling union(u, v).

Thanks to the path compression and union by rank optimizations we studied, the find and union operations are nearly constant time. This makes the cycle-detection part of the algorithm extremely fast.

Let's watch a detailed walkthrough that visualizes how these components (or "groups") are managed using Union-Find.

3. A Complete Example and Pseudocode

To solidify your understanding, let's review the algorithm's structure with pseudocode and a static visual example.

The Wikipedia article on Kruskal's algorithm provides a concise summary.

The pseudocode looks like this:

function Kruskal(Graph G) is
    F := ∅                           // F will be the set of edges in the MST
    for each vertex v in G.Vertices do
        MAKE-SET(v)
    
    Sort G.Edges into a list, ordered by increasing weight
    
    for each edge {u, v} in the sorted list do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F := F ∪ { {u, v} }
            UNION(FIND-SET(u), FIND-SET(v))  // Or simply UNION(u, v)
            
    return F

The image below provides another excellent step-by-step trace of the algorithm. On the right, you see the list of edges sorted by weight. The diagrams show which edge is being considered (red), which edges are already in the MST (black), and which are discarded because they form a cycle.

4. Complexity Analysis

Your preference for understanding the "why" includes analyzing performance. Let's break down the time complexity of Kruskal's algorithm. The main operations are:

1. Sorting Edges: Sorting $E$ edges takes $O(E\log E)$ time using a standard comparison-based sort like merge sort or quicksort.
2. Initializing Union-Find: Creating $V$ disjoint sets takes $O(V)$ time.
3. Iterating and Processing Edges: We iterate through all $E$ edges. For each edge, we perform two find operations and at most one union operation. With the optimizations from our last lesson, these operations have an amortized time complexity of $O(\alpha (V))$, where $\alpha$ is the extremely slow-growing inverse Ackermann function. The total time for this step is therefore $O(E\cdot \alpha (V))$.

The overall time complexity is the sum of these parts: $O(E\log E)+O(V)+O(E\cdot \alpha (V))$.
Since $\log E$ grows faster than $\alpha (V)$, the bottleneck is the initial edge sort.

Thus, the final time complexity of Kruskal's algorithm is $O(E\log E)$. This is often written as $O(E\log V)$ because in a connected graph, $E$ is at least $V-1$, and for dense graphs, $\log E$ is proportional to $\log V$.

5. Implementation Example

As a software engineer, you may find it helpful to see how these concepts translate into code. The following resource provides a clean Java implementation of Kruskal's algorithm, complete with the UnionFind class we've discussed.

This implementation brings together the Edge representation, the optimized UnionFind data structure, and the main greedy logic into a cohesive solution, showing a practical application of the theory.

Conclusion

In this lesson, we have successfully applied our knowledge of the Union-Find data structure to implement Kruskal's algorithm for finding a Minimum Spanning Tree.

Key Takeaways:

• Kruskal's algorithm is a greedy algorithm that builds an MST by iteratively adding the lowest-weight edge that does not form a cycle.
• The core of its efficiency lies in using a Union-Find (or DSU) data structure to track connected components and detect cycles in nearly constant time.
• The algorithm first sorts all edges by weight, which is the most computationally expensive step.
• The overall time complexity is dominated by sorting, resulting in $O(E\log E)$.

Preview of the Next Lesson:
Kruskal's algorithm is an "edge-centric" approach. What if we took a "vertex-centric" approach instead? In the next lesson, we will explore Prim's algorithm, another classic greedy algorithm for finding MSTs. It works by growing a single tree from an arbitrary starting vertex. We will compare its strategy and performance with Kruskal's, using a different data structure—the priority queue—as its core engine.