Algorithm Guidecomplexity: O(E log E)

Kruskal MST

Sorts all edges by ascending weight, then adopts only the edges that don't form a cycle to build a minimum spanning tree (MST). Cycle checks run in O(α) with union-find.

01Kruskal MST

Explore How It Works

Starting Kruskal. Sort all edges by ascending weight and place each node in its own set.

Start with the lightest edge, AB(1). A and B are in different sets, so joining them makes no cycle: add it to the MST and merge the sets.

BC(2) · different sets, so add it. {A,B} and C merge into one.

AC(3) · A and C are already in the same set. Joining them here would form a cycle, so reject it.

CD(4) · different sets, so add it. D joins {A,B,C}.

BD(5) · B and D are already one set too. That would form a cycle as well, so reject it.

DE(6) · the last set E joins. With 4 edges (5 nodes − 1), the MST is complete.

Done · MST = AB + BC + CD + DE, total weight 13. CE(7) is skipped since everything is already one set.

Live Python

1def kruskal(n, edges):

2 parent = list(range(n))

3 def find(x):

4 while parent[x] != x:

5 x = parent[x]

6 return x

7 mst, total = [], 0

# sorted: 1,2,3,4,5,6,7

8 for w, u, v in sorted(edges):

9 if find(u) != find(v):

10 parent[find(u)] = find(v)

11 mst.append((u, v))

12 total += w

13 return mst, total

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

Walks the edges from lightest to heaviest and keeps only those that do not close a cycle. The starting vertex makes no difference to the result.

💡In Plain Words

Sorts edges by weight and adopts only those that create no cycle.

Union-find checks for cycles quickly.

📍Where It's Used

–Least-cost network design
–building road and telecom networks

03 Python Implementation

A clean, readable reference implementation of the core logic of Kruskal MST.

core_implementation.py

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):
        if find(u) != find(v):
            parent[find(u)] = find(v)
            mst.append((u, v))
            total += w
    return mst, total

04 Frequently Asked Questions

FAQ

What is Kruskal MST?+

Sorts all edges by ascending weight, then adopts only the edges that don't form a cycle to build a minimum spanning tree (MST). Cycle checks run in O(α) with union-find.

What is the time complexity of Kruskal MST?+

The time complexity of Kruskal MST is O(E log E). Follow the step-by-step visualization to see exactly why.

Where is Kruskal MST used?+

Least-cost network design, building road and telecom networks.

What's a simple analogy for Kruskal MST?+

Walks the edges from lightest to heaviest and keeps only those that do not close a cycle. The starting vertex makes no difference to the result.

→ Graphs — see allRelated