What is a Minimum Spanning Tree?

An MST is a subset of edges that connects all vertices in a weighted graph with the minimum total edge weight and no cycles.

Prim's vs Kruskal's Algorithm?

Prim's builds the tree from a starting node. Kruskal's sorts all edges and adds them one by one (using Union-Find to avoid cycles).

What are MST applications?

Designing efficient networks (telecom, electrical grids), image segmentation, and cluster analysis.

Minimum Spanning Tree (MST)

A minimum spanning tree (MST) connects all vertices of a graph with the minimum total edge weight; Prim's and Kruskal's algorithms find it.

INIT

Tree so far — weight 0

No edge taken yet

Cheapest link into the tree

A:0

B:∞

C:∞

D:∞

E:∞

Every node starts unreachable except A, whose cost to join is 0.

Start the tree at A.

Algorithm

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

Prim's Steps:

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.

Kruskal's Steps:

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:

Green edge: Part of the tree built so far.
Blue edge: Currently being considered.
Red edge (Kruskal's): Rejected because it would form a cycle.
Green node: Already connected by the tree.
Blue nodes (Prim's): Solid blue is the node the step works from and pale blue is the neighbour whose cheapest link is being checked; the number above a node is that cheapest link.

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".

Sample Problems

Min Cost to Connect All Points

Standard MST problem (points on 2D plane).

Kruskal's MST (HackerRank)

Direct implementation challenge.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Bellman-Ford Algorithm

Floyd-Warshall Algorithm

Complexity

Time (Best)

Prim: O(E log V) | Kruskal: O(E log E)

Time (Average)

Prim: O(E log V) | Kruskal: O(E log E)

Time (Worst)

Prim: O(E log V) | Kruskal: O(E log E)

Space

O(V + E)

Minimum Spanning Tree (MST) Code

1// Prim's Algorithm
2function prim(n, edges) {
3  const adj = Array.from({length: n}, () => []);
4  for(const [u,v,w] of edges) {
5    adj[u].push([v,w]);
6    adj[v].push([u,w]);
7  }
8  const mst = [];
9  const visited = new Set();
10  const pq = [[0, 0, -1]]; // [weight, node, parent]
11  
12  while(visited.size < n && pq.length > 0) {
13    pq.sort((a,b) => a[0] - b[0]);
14    const [w, u, p] = pq.shift();
15    if(visited.has(u)) continue;
16    
17    visited.add(u);
18    if(p !== -1) mst.push([p, u, w]);
19    
20    for(const [v, weight] of adj[u]) {
21      if(!visited.has(v)) pq.push([weight, v, u]);
22    }
23  }
24  return mst;
25}
26
27// Kruskal's Algorithm with Union-Find
28function kruskal(n, edges) {
29  const parent = Array.from({length: n}, (_, i) => i);
30  const find = (i) => (parent[i] === i ? i : (parent[i] = find(parent[i])));
31  const union = (i, j) => {
32    const ri = find(i), rj = find(j);
33    if (ri === rj) return false;
34    parent[ri] = rj;
35    return true;
36  };
37
38  const sorted = [...edges].sort((a, b) => a[2] - b[2]); // Sort by weight
39  const mst = [];
40
41  for (const [u, v, w] of sorted) {
42    if (union(u, v)) {
43      mst.push([u, v, w]);
44    }
45  }
46  return mst;
47}

Related Lessons

Minimum Spanning Tree (MST)

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Min Cost to Connect All Points

Kruskal's MST (HackerRank)

AI resume checker — match your resume to the job description

Frequently Asked Questions

What is a Minimum Spanning Tree?

Prim's vs Kruskal's Algorithm?

What are MST applications?