DSA with Go — Part 33: Kruskal’s Algorithm — Building a Minimum Spanning Tree with Union-Find

Introduction

In the previous article, we learned about Prim’s Algorithm, one of the two most popular algorithms for finding a Minimum Spanning Tree (MST).

Today, we’ll study the second one:

Kruskal’s Algorithm

Although Prim’s and Kruskal’s Algorithms solve the same problem, they take completely different approaches.

• Prim’s Algorithm grows a tree one vertex at a time.
• Kruskal’s Algorithm grows a forest by selecting the smallest edges first.

Kruskal’s Algorithm introduces another extremely important data structure:

Disjoint Set Union (DSU)

also known as

• Union-Find
• Disjoint Set
• Union Find Data Structure

This data structure appears in many interview questions beyond Minimum Spanning Trees.

By the end of this article, you’ll understand:

• What Kruskal’s Algorithm is
• Why cycle detection is necessary
• What Union-Find is
• Path Compression
• Union by Rank
• Complete Go implementation
• Time and Space Complexity
• Real-world applications

Let’s begin.

The Idea Behind Kruskal’s Algorithm

Suppose we have this graph.

      A
     / \
   2/   \3
   B--1--C
    \    /
    4\  /5
      D

Instead of starting from a node,

Kruskal starts by sorting every edge.

Sorted edges:

B-C = 1
A-B = 2
A-C = 3
B-D = 4
C-D = 5

Then,

process edges from smallest to largest.

If an edge creates a cycle,

skip it.

Otherwise,

add it to the MST.

Step-by-Step Example

Sorted edges:

B-C = 1
A-B = 2
A-C = 3
B-D = 4
C-D = 5

Step 1

Choose:

B-C

Current MST:

B ----- C

Cost:

1

Step 2

Choose:

A-B

Current MST:

A
|
B
|
C

Cost:

3

Step 3

Next edge:

A-C

Would it create a cycle?

Yes.

Skip it.

Step 4

Next edge:

B-D

No cycle.

Add it.

Final MST:

A
|
B
| \
C  D

Total cost:

7

Done.

The Biggest Challenge

How do we know whether adding an edge creates a cycle?

Example:

A
|
B
|
C

Now suppose we add:

A ----- C

Cycle created.

We need a fast way to determine whether two vertices are already connected.

That’s exactly what Union-Find does.

What is Union-Find?

Union-Find keeps track of connected components.

Initially:

A
B
C
D

Every node belongs to its own set.

Parent array:

A → A
B → B
C → C
D → D

Union Operation

Suppose we connect:

A
|
B

Now:

Parent[B] = A

A and B belong to the same group.

Find Operation

The Find() function answers:

Which set does this node belong to?

Example:

A
|
B
|
C

Find:

Find(C)

returns:

A

because A is the root.

If two nodes have the same root,

they already belong to the same connected component.

Adding another edge between them creates a cycle.

Path Compression

Suppose we have:

A
|
B
|
C
|
D

Finding D requires:

D
↓
C
↓
B
↓
A

That’s slow.

Get Anila Soman’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

After Path Compression:

A
| \ \
B C D

Now every node points directly to the root.

Future Find() operations become much faster.

Union by Rank

Suppose we merge two trees.

Bad approach:

A
|
B
|
C
|
D
|
E

Very deep tree.

Instead,

attach the smaller tree under the larger tree.

This technique is called:

Union by Rank

(or Union by Size)

It keeps the tree shallow,

making Find() nearly constant time.

Union-Find Implementation

type DSU struct {
	parent map[string]string
	rank   map[string]int
}

Initialization:

func NewDSU(vertices []string) *DSU {

    parent := make(map[string]string)
    rank := make(map[string]int)
    for _, vertex := range vertices {
        parent[vertex] = vertex
        rank[vertex] = 0
    }
   return &DSU{
      parent: parent,
      rank:   rank,
   }
}

Find with Path Compression

func (d *DSU) Find(x string) string {

    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x])
    }
   return d.parent[x]
}

Union by Rank

func (d *DSU) Union(x, y string) {

      rootX := d.Find(x)
      rootY := d.Find(y)
      if rootX == rootY {
          return
      }
      if d.rank[rootX] < d.rank[rootY] {
          d.parent[rootX] = rootY
      } else if d.rank[rootX] > d.rank[rootY] {
          d.parent[rootY] = rootX
      } else {
          d.parent[rootY] = rootX
          d.rank[rootX]++
      }
}

Kruskal’s Algorithm

Edge structure:

type Edge struct {
	From   string
	To     string
	Weight int
}

Implementation:

func Kruskal(vertices []string, edges []Edge) int {
      sort.Slice(edges, func(i, j int) bool {
      return edges[i].Weight < edges[j].Weight
      })
       dsu := NewDSU(vertices)
       totalCost := 0
       for _, edge := range edges {
          if dsu.Find(edge.From) != dsu.Find(edge.To) {
             dsu.Union(edge.From, edge.To)
             totalCost += edge.Weight
          }
       }
   return totalCost
}

Usage:

vertices := []string{"A", "B", "C", "D"}

edges := []Edge{
         {"A", "B", 2},
         {"A", "C", 3},
         {"B", "C", 1},
         {"B", "D", 4},
         {"C", "D", 5},
}
cost := Kruskal(vertices, edges)
fmt.Println(cost)

Output:

7

Time Complexity

Sorting edges:

O(E log E)

Union-Find operations:

Almost constant time:

O(α(V))

where:

α(V)

is the Inverse Ackermann Function, which grows so slowly that it’s effectively constant for any practical input size.

Overall:

O(E log E)

Space Complexity

We store:

• Parent map
• Rank map

Total:

O(V)

Prim vs Kruskal

Both algorithms produce a valid Minimum Spanning Tree.

Common Interview Problems

Union-Find and Kruskal appear in many coding interviews.

Examples:

• Redundant Connection
• Number of Connected Components
• Accounts Merge
• Graph Valid Tree
• Connecting Cities With Minimum Cost
• Min Cost to Connect All Points

Learning Union-Find unlocks an entire family of graph problems.

Real-World Applications

Network Design

Connecting routers with minimum cable cost.

Electrical Grids

Designing power transmission networks.

Road Construction

Building roads while minimizing construction expenses.

Image Processing

Union-Find is used in connected-component labeling to identify regions in images.

Backend Engineering

Union-Find is useful for:

• Cluster management
• Network connectivity analysis
• Distributed system partition detection
• Infrastructure topology management
• Resource grouping

Even outside MSTs, Union-Find is a valuable tool whenever you need to maintain dynamically connected components.

Common Mistakes

Forgetting to Sort Edges

Kruskal’s Algorithm only works when edges are processed in ascending order of weight.

Skipping Cycle Detection

Without Union-Find (or another cycle detection mechanism), the resulting graph may contain cycles and will no longer be a tree.

Not Using Path Compression

A plain Union-Find works correctly but can become much slower on large inputs.

Always combine:

• Path Compression
• Union by Rank (or Size)

for near-optimal performance.

Assuming Kruskal Builds a Path

Kruskal builds a tree, not a shortest path.

It optimizes the total cost of connecting all vertices, not the distance between two specific nodes.

Key Takeaways

• Kruskal’s Algorithm builds a Minimum Spanning Tree by processing edges in ascending order.
• It uses Union-Find (Disjoint Set Union) to detect cycles efficiently.
• Path Compression and Union by Rank make Union-Find extremely efficient.
• Overall Time Complexity is O(E log E).
• Kruskal is particularly effective for sparse graphs.
• Union-Find is a powerful data structure that appears in many interview problems beyond MSTs.

🎉 Congratulations!

You’ve now mastered the major graph algorithms:

• Graph Fundamentals
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Cycle Detection
• Topological Sort
• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• Prim’s Algorithm
• Kruskal’s Algorithm
• Union-Find (Disjoint Set Union)

At this point, you have a strong foundation in graph theory for coding interviews and backend engineering.

See you in Part 34.