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

Kruskal's Algorithm: Union-Find Data Structure

Learn how the union-find (disjoint set) data structure enables efficient cycle detection in Kruskal's algorithm.

Kruskal's Algorithm: Union-Find Data Structure

What You'll Learn

You'll discover how the union-find (disjoint set) data structure makes Kruskal's algorithm efficient by quickly detecting cycles as you add edges to build a minimum spanning tree.

Why Union-Find Matters for Kruskal's

Kruskal's algorithm sorts edges by weight and tries to add them one by one to build an MST. But there's a catch: you can only add an edge if it doesn't create a cycle. Without an efficient way to check for cycles, you'd need to search the growing tree after each edge addition—slow and inefficient!

What Union-Find Does

Union-Find maintains a collection of disjoint sets (groups of vertices that aren't connected). Each set represents a connected component in your partial MST.

Two key operations:

  • Find: Determine which set (component) a vertex belongs to
  • Union: Merge two sets into one

The Cycle Detection Trick:
Before adding edge (u, v):

  1. Use Find(u) and Find(v) to get their component leaders
  2. If they're the same, u and v are already connected—adding this edge creates a cycle, so skip it
  3. If they're different, u and v are in separate components—safe to add! Then Union their sets

Analogy: Club Membership

Think of vertices as people and components as clubs. Find tells you which club someone belongs to. Union merges two clubs. You can only introduce two people (add an edge) if they're in different clubs—otherwise you're creating a redundant connection within the same club (a cycle).

Efficiency Win

Union-Find operations run in nearly constant time (almost O(1) with optimizations), making cycle detection blazingly fast compared to graph traversal methods.

Key Takeaway: Union-Find enables Kruskal's algorithm to efficiently detect cycles by tracking which vertices belong to the same connected component—if an edge connects two vertices already in the same component, it would create a cycle and should be rejected.