IntermediateGraphs

Minimum Spanning Tree

Build MST using Kruskal or Prim algorithms

Time: O(E log V)
Space: O(V+E)
Pattern Overview

Core Idea

Pick edges that connect new components with minimum weight without forming cycles.

When to Use

Use on connected weighted undirected graphs to minimize total edge cost.

General Recognition Cues
General indicators that this pattern might be applicable
  • Connect all with min cost
  • No cycles allowed
  • Undirected weighted graph
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Kruskal

Sort edges and union if components differ

When to Use This Variant
  • Edge-centric
Use Case
Sparse graphs
Advantages
  • Simple with DSU
  • O(E log E)
Implementation
def kruskal(n, edges):
    # edges: (w,u,v)
    dsu=DSU(n); edges.sort()
    cost=0; mst=[]
    for w,u,v in edges:
        if dsu.union(u,v): cost+=w; mst.append((u,v,w))
    return cost, mst
2

Prim

Grow from a node using a min-heap

When to Use This Variant
  • Vertex-centric
Use Case
Dense graphs
Advantages
  • O(E log V)
  • Local frontier
Implementation
import heapq
def prim(n, adj):
    # adj[u] = [(v,w), ...]; assumes connected
    vis=[False]*n; vis[0]=True; h=[]
    for v,w in adj[0]: heapq.heappush(h, (w, 0, v))
    cost=0; cnt=1
    while h and cnt<n:
        w,u,v = heapq.heappop(h)
        if vis[v]: continue
        vis[v]=True; cost+=w; cnt+=1
        for nv,nw in adj[v]:
            if not vis[nv]: heapq.heappush(h, (nw, v, nv))
    return cost
Common Pitfalls
Watch out for these common mistakes
  • Not handling disconnected graphs
  • Indexing DSU wrong
  • Prim's PQ updates
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(E log V)

Sorting or PQ dominates.

Space Complexity
O(V+E)

Graph + DSU/PQ.

Ready to test your knowledge?

Test your pattern recognition with interactive questions