Kruskal's Minimum Spanning Tree
Add cheapest edges without cycles.
Kruskal's Minimum Spanning Tree is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What an MST Is
A minimum spanning tree connects every vertex using the cheapest total edge weight, with no cycles. Think wiring a town for the least cost. 🌲
Kruskal's Core Idea
Kruskal's algorithm is pure greed: keep adding the cheapest edge that does not create a cycle until the whole graph is joined.
Step One: Sort Edges
First sort every edge by weight, smallest first. Greedily preferring cheap edges is what makes the final total minimal.
edges.sort() # (weight, u, v)Why DSU Fits Perfectly
Adding an edge forms a cycle only if both endpoints are already connected. DSU answers that connectivity test in near-constant time. 🤝
Walk the Sorted Edges
Go through edges from cheapest to costliest. For each one, check whether its two endpoints already share a root in the DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Accept or Reject
If the roots differ, the edge links two separate pieces, so accept it and union them. If the roots match, skip it to avoid a cycle.
if ru != rv:
union(u, v)
total += wKnow When to Stop
A spanning tree of n vertices has exactly n minus 1 edges. Once you have accepted that many, you can stop early.
Detecting Disconnection
If you finish all edges with fewer than n minus 1 accepted, the graph is disconnected and no spanning tree exists.
The Time Cost
Sorting dominates, so Kruskal's runs in O(E log E). The DSU operations are so cheap they barely add to that total.
Why Greedy Is Correct
The cut property guarantees the lightest edge crossing any split is safe to add, which is exactly why picking cheapest-first never goes wrong.
When to Reach for Kruskal
Kruskal's shines on sparse graphs given as an edge list, the format most contest problems hand you directly. ⚡
Quick Check
Decide what tells Kruskal's to reject an edge.
Recap
You built Kruskal's MST: sort edges, add the cheapest that joins two components via DSU, and stop at n minus 1 edges. 🎉
Frequently asked questions
Is the “Kruskal's Minimum Spanning Tree” lesson free?
Yes — the full text of “Kruskal's Minimum Spanning Tree” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Kruskal's Minimum Spanning Tree”?
Add cheapest edges without cycles. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Kruskal's Minimum Spanning Tree” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- DSU with Path Compression
- Union by Rank and Components
- Kruskal's Minimum Spanning Tree
- Prim's MST with a Heap