Kruskal's Algorithm and Union-Find

DSA · Graphs

Theory

Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight and adding each edge if it does not create a cycle. It uses a union-find (disjoint set) structure to check quickly whether two vertices are already connected: find returns a set's representative and union merges two sets. With path compression and union by rank, each union-find operation is almost O(1), so Kruskal runs in O(E log E), dominated by sorting.

Why we use it

Union-find answers "are these connected?" extremely fast, and Kruskal is simple and efficient for sparse graphs.

When to use it

Use union-find for connected components, cycle detection, network connectivity, merging accounts, and Kruskal's MST.

How it works

  1. Sort edges by weight
  2. Take the next cheapest edge (u, v)
  3. find(u) == find(v)? Yes: Skip (would form a cycle). No: union(u, v), add edge.
  4. Tree has V - 1 edges? Yes: Done. No: Next edge.

Syntax

parent[x] = x initially
find(x): follow parents to the root (compress path)
union(a, b): attach one root under the other

Kruskal: sort edges; for each (u, v, w):
    if find(u) != find(v): union(u, v); take edge

Example

parent = {}
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]     # path compression
        x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    parent[ra] = rb
    return True

edges = [(1, "B", "C"), (2, "A", "B"), (3, "A", "C"), (4, "B", "D"), (5, "C", "D")]
for _, u, v in edges:
    parent.setdefault(u, u); parent.setdefault(v, v)

mst, total = [], 0
for w, u, v in sorted(edges):
    if union(u, v):
        mst.append((u, v, w)); total += w
print("Kruskal MST:", mst, "| cost:", total)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic