Minimum Spanning Tree (MST) is a greedy graph pattern.

It applies to:

Connected, undirected, weighted graphs.

The goal is to connect every vertex with:

Minimum total edge weight
No cycles
Exactly V - 1 selected edges

Mental Trigger

“Connect all nodes with minimum total cost” = MST

Then choose:

Edges → Kruskal
Growing from a node → Prim

Pattern Table

Pattern	Algorithm	Main Idea
Edge-based MST	Kruskal	Sort + DSU
Node-based MST	Prim	Min Heap
Cycle avoidance	DSU	Union-Find
Dense graph	Prim	Expand cheapest boundary edge
Sparse graph	Kruskal	Process sorted edges

1. Generic MST Decision Template

Before coding, ask:

Need minimum cost to connect ALL vertices?
            ↓
           MST
        ↙       ↘
   Edge list   Graph
      ↓           ↓
   Kruskal      Prim

Everything else is a modification of one of these two templates.

Pattern 1: Kruskal’s Algorithm

Kruskal builds the MST by repeatedly choosing the cheapest edge that does not create a cycle.

Sorted edges, greedy picks, one DSU rejection — the whole algorithm in six steps:

Kruskal's MST

Minimum spanning tree by adding cheapest edges that don't close a cycle.

Sort edges ascending; for each, take it only if its endpoints are in different DSU sets (union them), else reject — taking it would form a cycle. Stop at n−1 edges. O(E log E) dominated by the sort.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort edges by weight ascending
                      
                        2
                        mst = []; dsu = new UnionFind(n)
                      
                        3
                        for (u, v, w) in edges:
                      
                        4
                          if find(u) != find(v):
                      
                        5
                            mst.add(edge); union(u, v)
                      
                        6
                        stop when mst has n-1 edges

Java Template

class DSU {
    int[] parent;
    int[] size;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    boolean union(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (pa == pb) {
            return false;
        }

        if (size[pa] < size[pb]) {
            parent[pa] = pb;
            size[pb] += size[pa];
        } else {
            parent[pb] = pa;
            size[pa] += size[pb];
        }

        return true;
    }
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def union(self, a, b):
        pa = self.find(a)
        pb = self.find(b)

        if pa == pb:
            return False

        if self.size[pa] < self.size[pb]:
            self.parent[pa] = pb
            self.size[pb] += self.size[pa]
        else:
            self.parent[pb] = pa
            self.size[pa] += self.size[pb]

        return True

struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    bool unite(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (pa == pb) {
            return false;
        }

        if (size[pa] < size[pb]) {
            parent[pa] = pb;
            size[pb] += size[pa];
        } else {
            parent[pb] = pa;
            size[pa] += size[pb];
        }

        return true;
    }
};

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }

    return this.parent[x];
  }

  union(a, b) {
    const pa = this.find(a);
    const pb = this.find(b);

    if (pa === pb) {
      return false;
    }

    if (this.size[pa] < this.size[pb]) {
      this.parent[pa] = pb;
      this.size[pb] += this.size[pa];
    } else {
      this.parent[pb] = pa;
      this.size[pa] += this.size[pb];
    }

    return true;
  }
}

public int kruskalMST(int n, int[][] edges) {

    Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

    DSU dsu = new DSU(n);

    int cost = 0;
    int edgesUsed = 0;

    for (int[] edge : edges) {

        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (dsu.union(u, v)) {
            cost += weight;
            edgesUsed++;
        }

        if (edgesUsed == n - 1) {
            break;
        }
    }

    return edgesUsed == n - 1 ? cost : -1;
}

def kruskal_mst(n, edges):

    edges.sort(key=lambda edge: edge[2])

    dsu = DSU(n)

    cost = 0
    edges_used = 0

    for u, v, weight in edges:

        if dsu.union(u, v):
            cost += weight
            edges_used += 1

        if edges_used == n - 1:
            break

    return cost if edges_used == n - 1 else -1

int kruskalMST(int n, vector<vector<int>>& edges) {

    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b) { return a[2] < b[2]; });

    DSU dsu(n);

    int cost = 0;
    int edgesUsed = 0;

    for (auto& edge : edges) {

        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (dsu.unite(u, v)) {
            cost += weight;
            edgesUsed++;
        }

        if (edgesUsed == n - 1) {
            break;
        }
    }

    return edgesUsed == n - 1 ? cost : -1;
}

function kruskalMST(n, edges) {
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(n);

  let cost = 0;
  let edgesUsed = 0;

  for (const [u, v, weight] of edges) {
    if (dsu.union(u, v)) {
      cost += weight;
      edgesUsed++;
    }

    if (edgesUsed === n - 1) {
      break;
    }
  }

  return edgesUsed === n - 1 ? cost : -1;
}

What Changed from Generic DSU?

1. Sort edges

Arrays.sort(edges,
    (a, b) -> Integer.compare(a[2], b[2]));

because Kruskal processes edges from cheapest to most expensive.

2. Use `union()` as a cycle check

if (dsu.union(u, v))

If both vertices already belong to the same component:

return false;

That edge would create a cycle.

3. Stop after `n - 1` edges

A spanning tree always contains exactly:

V - 1 edges

Kruskal = Sort edges → Union safe edges → Stop at V - 1 edges.

Pattern 2: Prim’s Algorithm

Prim grows one tree outward.

At every step:

Choose the cheapest edge connecting the current tree to an unvisited vertex.

Java Template

public int primMST(List<List<int[]>> graph, int n) {

    boolean[] visited = new boolean[n];

    PriorityQueue<int[]> pq =
        new PriorityQueue<>(
            (a, b) -> Integer.compare(a[1], b[1])
        );

    // {node, edgeWeight}
    pq.offer(new int[]{0, 0});

    int cost = 0;
    int nodesUsed = 0;

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int node = current[0];
        int weight = current[1];

        if (visited[node]) {
            continue;
        }

        visited[node] = true;
        cost += weight;
        nodesUsed++;

        for (int[] edge : graph.get(node)) {

            int neighbor = edge[0];
            int edgeWeight = edge[1];

            if (!visited[neighbor]) {
                pq.offer(
                    new int[]{neighbor, edgeWeight}
                );
            }
        }
    }

    return nodesUsed == n ? cost : -1;
}

import heapq

def prim_mst(graph, n):

    visited = [False] * n

    # (edge_weight, node)
    pq = [(0, 0)]

    cost = 0
    nodes_used = 0

    while pq:

        weight, node = heapq.heappop(pq)

        if visited[node]:
            continue

        visited[node] = True
        cost += weight
        nodes_used += 1

        for neighbor, edge_weight in graph[node]:

            if not visited[neighbor]:
                heapq.heappush(
                    pq, (edge_weight, neighbor)
                )

    return cost if nodes_used == n else -1

int primMST(vector<vector<pair<int, int>>>& graph, int n) {
    vector<bool> visited(n, false);

    // {edgeWeight, node}
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>> pq;

    pq.push({0, 0});

    int cost = 0;
    int nodesUsed = 0;

    while (!pq.empty()) {

        auto [weight, node] = pq.top();
        pq.pop();

        if (visited[node]) {
            continue;
        }

        visited[node] = true;
        cost += weight;
        nodesUsed++;

        for (auto& [neighbor, edgeWeight] : graph[node]) {

            if (!visited[neighbor]) {
                pq.push({edgeWeight, neighbor});
            }
        }
    }

    return nodesUsed == n ? cost : -1;
}

function primMST(graph, n) {
  const visited = new Array(n).fill(false);

  // ponytail: array + sort stands in for a binary heap; swap in a real heap if E gets large
  const pq = [[0, 0]];

  let cost = 0;
  let nodesUsed = 0;

  while (pq.length > 0) {
    pq.sort((a, b) => a[1] - b[1]);

    const [node, weight] = pq.shift();

    if (visited[node]) {
      continue;
    }

    visited[node] = true;
    cost += weight;
    nodesUsed++;

    for (const [neighbor, edgeWeight] of graph[node]) {
      if (!visited[neighbor]) {
        pq.push([neighbor, edgeWeight]);
      }
    }
  }

  return nodesUsed === n ? cost : -1;
}

What Changed from Generic BFS?

1. Queue → Priority Queue

BFS:

Queue<Integer>

Prim:

PriorityQueue<int[]>

because we need the cheapest available edge, not the next node in FIFO order.

2. Level order → Minimum boundary edge

BFS asks:

Which node comes next?

Prim asks:

Which edge gives the cheapest way to expand the current tree?

3. Add edge weight to cost

cost += weight;

The selected edge becomes part of the MST.

Prim = Grow one tree by repeatedly choosing the cheapest boundary edge.

Pattern 3: Prim with an Adjacency Matrix

For dense graphs, Prim can also be implemented without a heap.

Java Template

public int primMatrix(int[][] graph) {

    int n = graph.length;

    int[] minEdge = new int[n];
    boolean[] used = new boolean[n];

    Arrays.fill(minEdge, Integer.MAX_VALUE);

    minEdge[0] = 0;

    int cost = 0;

    for (int count = 0; count < n; count++) {

        int node = -1;

        for (int i = 0; i < n; i++) {
            if (!used[i] &&
                (node == -1 || minEdge[i] < minEdge[node])) {
                node = i;
            }
        }

        if (node == -1 ||
            minEdge[node] == Integer.MAX_VALUE) {
            return -1;
        }

        used[node] = true;
        cost += minEdge[node];

        for (int neighbor = 0; neighbor < n; neighbor++) {

            if (!used[neighbor] &&
                graph[node][neighbor] < minEdge[neighbor]) {

                minEdge[neighbor] =
                    graph[node][neighbor];
            }
        }
    }

    return cost;
}

def prim_matrix(graph):
    n = len(graph)

    min_edge = [float('inf')] * n
    used = [False] * n

    min_edge[0] = 0

    cost = 0

    for _ in range(n):

        node = -1

        for i in range(n):
            if not used[i] and (
                node == -1 or min_edge[i] < min_edge[node]
            ):
                node = i

        if node == -1 or min_edge[node] == float('inf'):
            return -1

        used[node] = True
        cost += min_edge[node]

        for neighbor in range(n):
            if not used[neighbor] and (
                graph[node][neighbor] < min_edge[neighbor]
            ):
                min_edge[neighbor] = graph[node][neighbor]

    return cost

int primMatrix(vector<vector<int>>& graph) {
    int n = graph.size();

    vector<int> minEdge(n, INT_MAX);
    vector<bool> used(n, false);

    minEdge[0] = 0;

    int cost = 0;

    for (int count = 0; count < n; count++) {

        int node = -1;

        for (int i = 0; i < n; i++) {
            if (!used[i] &&
                (node == -1 || minEdge[i] < minEdge[node])) {
                node = i;
            }
        }

        if (node == -1 ||
            minEdge[node] == INT_MAX) {
            return -1;
        }

        used[node] = true;
        cost += minEdge[node];

        for (int neighbor = 0; neighbor < n; neighbor++) {

            if (!used[neighbor] &&
                graph[node][neighbor] < minEdge[neighbor]) {

                minEdge[neighbor] =
                    graph[node][neighbor];
            }
        }
    }

    return cost;
}

function primMatrix(graph) {
  const n = graph.length;

  const minEdge = new Array(n).fill(Infinity);
  const used = new Array(n).fill(false);

  minEdge[0] = 0;

  let cost = 0;

  for (let count = 0; count < n; count++) {
    let node = -1;

    for (let i = 0; i < n; i++) {
      if (!used[i] && (node === -1 || minEdge[i] < minEdge[node])) {
        node = i;
      }
    }

    if (node === -1 || minEdge[node] === Infinity) {
      return -1;
    }

    used[node] = true;
    cost += minEdge[node];

    for (let neighbor = 0; neighbor < n; neighbor++) {
      if (!used[neighbor] && graph[node][neighbor] < minEdge[neighbor]) {
        minEdge[neighbor] = graph[node][neighbor];
      }
    }
  }

  return cost;
}

What Changed from Heap-Based Prim?

Instead of:

PriorityQueue

we explicitly search for the unvisited vertex with the smallest connecting edge.

Complexity

Heap Prim:    O(E log V)
Matrix Prim:  O(V²)

Dense graph + matrix → O(V²) Prim can be simple and effective.

Pattern 4: MST Edge List

Sometimes the problem gives edges directly:

[u, v, weight]

This strongly suggests:

Kruskal.

Recognition

int[][] edges

usually makes this pattern convenient:

Sort → DSU → MST

Edge list → Think Kruskal first.

Pattern 5: MST from an Adjacency List

If the graph is already represented as:

List<List<int[]>> graph

Prim is often natural.

Graph
 ↓
Start from any node
 ↓
Min Heap
 ↓
Cheapest boundary edge
 ↓
Expand

Adjacency list + growing tree → Think Prim.

Kruskal vs Prim

Feature	Kruskal	Prim
Strategy	Edge-based	Tree/node-based
Main structure	DSU	Priority Queue
Starts from node	No	Yes
Sort all edges	Yes	No
Cycle handling	DSU	Visited
Typical input	Edge list	Adjacency list
Sparse graph	Often convenient	Good
Dense graph	Can be expensive	Often attractive

MST Pattern Evolution

Graph
   ↓
Need minimum cost to connect ALL nodes
   ↓
MST
   ↓
Choose representation
   ↓
Edge list ─────────→ Kruskal
   │                   ↓
   │              Sort edges
   │                   ↓
   │                  DSU
   │                   ↓
   │             Skip cycles
   │
   └── Adjacency list → Prim
                         ↓
                     Min Heap
                         ↓
                Cheapest boundary edge
                         ↓
                    Grow tree

Common Mistakes

1. Using MST for a shortest-path problem

These are different problems.

Shortest Path

Minimize the cost from one source to a destination.

Use:

BFS
Dijkstra
Bellman-Ford

MST

Minimize the total cost to connect every vertex.

Use:

Kruskal
Prim

2. Forgetting that MST is for undirected graphs

Standard MST applies to:

Connected
+
Undirected
+
Weighted

Directed minimum spanning structures require different algorithms.

3. Forgetting disconnected graphs

A disconnected graph has no spanning tree.

Track:

edgesUsed == n - 1

or:

nodesUsed == n

to verify that everything was connected.

4. Unsafe integer comparator

Avoid:

(a, b) -> a[2] - b[2]

because subtraction can overflow.

Prefer:

(a, b) -> Integer.compare(a[2], b[2])

5. Forgetting DSU cycle detection

Kruskal cannot simply add every edge.

Wrong:

cost += weight;

Correct:

if (dsu.union(u, v)) {
    cost += weight;
}

Recognition Cheat Sheet

If you see…	Think…
Connect all nodes	MST
Minimum connection cost	MST
No cycles	MST / DSU
Edge list	Kruskal
Sort edges	Kruskal
Union-Find	Kruskal
Grow from a node	Prim
Cheapest boundary edge	Prim
Min heap	Prim
Shortest path from A to B	Dijkstra/BFS
Directed graph	Usually not standard MST

MST vs Shortest Path

This distinction is extremely important.

Suppose:

A --1-- B --1-- C
 \             /
  -----10------

Shortest path A → C

A → B → C
cost = 2

MST

Choose:

A-B = 1
B-C = 1

Total:

They happen to match here, but MST and shortest path optimize different things.

Shortest path minimizes one route. MST minimizes the total cost of connecting the entire graph.

Earn Premium with Referrals

Mental Trigger

Pattern Table

1. Generic MST Decision Template

Pattern 1: Kruskal’s Algorithm

Kruskal's MST

Java Template

What Changed from Generic DSU?

1. Sort edges

2. Use union() as a cycle check

3. Stop after n - 1 edges

Pattern 2: Prim’s Algorithm

Java Template

What Changed from Generic BFS?

1. Queue → Priority Queue

2. Level order → Minimum boundary edge

3. Add edge weight to cost

Pattern 3: Prim with an Adjacency Matrix

Java Template

What Changed from Heap-Based Prim?

Complexity

Pattern 4: MST Edge List

Recognition

Pattern 5: MST from an Adjacency List

Kruskal vs Prim

MST Pattern Evolution

Common Mistakes

1. Using MST for a shortest-path problem

Shortest Path

MST

2. Forgetting that MST is for undirected graphs

3. Forgetting disconnected graphs

4. Unsafe integer comparator

5. Forgetting DSU cycle detection

Recognition Cheat Sheet

MST vs Shortest Path

Shortest path A → C

MST

Premium Content

My Private Notes

2. Use `union()` as a cycle check

3. Stop after `n - 1` edges