Minimum Spanning Tree (MST)
Learn how to connect all vertices in a graph with the minimum total edge weight using Prim's and Kruskal's algorithms.
Ready to start
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Prim's Algorithm: Imagine a mold spreading from a single point. It keeps adding the nearest node to the growing blob until everything is covered.
Kruskal's Algorithm: Imagine building bridges. You always build the cheapest bridge available anywhere on the map, unless it connects two islands that are already connected (which would be redundant).
Concept
A Spanning Tree is a subgraph that connects all vertices without any cycles. A Minimum Spanning Tree (MST) is the spanning tree with the lowest total edge weight.
- Prim's (Node-based): Grows a single tree from a starting node. Best for dense graphs.
- Kruskal's (Edge-based): Adds edges from lightest to heaviest, merging disjoint sets. Best for sparse graphs.
How it Works
- Start with an arbitrary node.
- Add all connected edges to a Priority Queue.
- Pick the smallest edge connecting a visited node to an unvisited one.
- Add the new node to the MST set.
- Repeat until all nodes are visited.
- Sort all edges by weight (ascending).
- Iterate through sorted edges.
- For each edge (u, v), check if u and v are already connected (using Union-Find).
- If not connected, add edge to MST and union the sets.
- If connected, skip to avoid cycles.
Step-by-Step Breakdown
Watch the visualization:
- Emerald Edge: Part of the finalized MST.
- Orange Edge: Currently being considered / processed.
- Red Edge (Kruskal's): Rejected because it forms a cycle.
When to Use
Applications:
- Network design (telecom cables, water pipes, road networks).
- Clustering algorithms in Machine Learning.
- Approximation algorithms for NP-hard problems (like TSP).
When NOT to Use
- Shortest Paths: MST minimizes total weight, not the path distance between two specific nodes (use Dijkstra).
- Directed Graphs: Standard Prim's/Kruskal's apply to undirected graphs. For directed MST, use the Chu-Liu/Edmonds algorithm.
How to Identify
"Connect all points with minimum cost", "Design a network with least cable".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.