Back to course

Lesson 51: Kruskal's Algorithm: Using the Disjoint Set Union (DSU) structure

Algorithms: From Zero to Hero (A Beginner's Guide)

51. Kruskal's Algorithm: Using the Disjoint Set Union (DSU) structure

Kruskal's is another greedy algorithm for finding the MST, but it focuses on edges rather than vertices.

Kruskal's Algorithm Steps

  1. Sort all edges in the graph by weight in non-decreasing order.
  2. Initialize the MST set (empty).
  3. Iterate through the sorted edges:
    • For the current edge (U, V), check if U and V are already connected (i.e., in the same component).
    • If they are not connected (adding the edge would not create a cycle), add the edge to the MST set and combine the two components.

Disjoint Set Union (DSU)

Kruskal's relies heavily on the DSU data structure (also known as Union-Find). DSU allows for two highly efficient O(α(N)) operations (where α is the inverse Ackermann function, which is nearly constant time):

  1. Find: Determine which set an element belongs to (useful for cycle detection).
  2. Union: Merge two sets into one (useful for adding an edge).

This makes Kruskal's very efficient, often O(E log E) dominated by the initial sorting.