Pattern #61

Connect every node with minimum total edge cost using Kruskal or Prim, while preserving the V − 1 edge and no-cycle invariants.

Must Solve

15 core MST questions.

1. 1.Min Cost to Connect All Points
   medium
2. 2.Connecting Cities With Minimum Cost
   medium
3. 3.Optimize Water Distribution in a Village
   medium
4. 4.Minimum Cost to Connect All Nodes
   medium
5. 5.Kruskal's Algorithm
   medium
6. 6.Prim's Algorithm
   medium
7. 7.Find Critical and Pseudo-Critical Edges in MST
   hard
8. 8.Minimum Cost to Connect Points with Manhattan Distance
   hard
9. 9.Minimum Spanning Tree from Edge List
   hard
10. 10.Minimum Spanning Tree from Adjacency List
    hard
11. 11.Check Whether an Edge Belongs to an MST
    hard
12. 12.Minimum Cost Network Connection
    hard
13. 13.Minimum Cost to Connect Islands / Components
    hard
14. 14.Maximum Spanning Tree — Variant
    hard
15. 15.Minimum Spanning Forest
    hard

Also Important

6 advanced network-design variants.

1. 16.Second Minimum Spanning Tree — Advanced
   medium
2. 17.MST with Pre-Connected Components
   medium
3. 18.MST with Optional Connections
   medium
4. 19.MST with Virtual Node
   medium
5. 20.Manhattan MST Optimization — Advanced
   medium
6. 21.Dynamic MST — Advanced
   medium

How to Think

Spanning tree:
• contains every vertex
• has exactly V − 1 edges
• is connected
• has no cycle

MST minimizes the sum of those V − 1 edge weights.

Go Quick Reference — Kruskal & Prim

sort.Slice(edges, func(i, j int) bool {
    return edges[i].w < edges[j].w
})
for _, e := range edges {
    if dsu.Union(e.u, e.v) {
        cost += e.w
        used++
    }
}

heap.Push(&pq, Edge{w: 0, to: start})
for pq.Len() > 0 {
    e := heap.Pop(&pq).(Edge)
    if visited[e.to] { continue }
    visited[e.to] = true
    cost += e.w
    // push edges from e.to
}

MST Patterns

MST → connect every vertex
Accepted edges → exactly V − 1
Cycle → reject
Kruskal → sorted edges + DSU
Prim → frontier heap + visited

Complexity

Kruskal: O(E log E) time, O(V) DSU space
Heap Prim: O(E log V) time, O(V + E) space
Matrix Prim: O(V²) time, O(V) extra space

Common Interview Mistakes

• Confusing MST with shortest path

• Forgetting an MST needs V − 1 accepted edges

• Allowing a cycle

• Not checking that all vertices became connected

• Using Dijkstra to minimize total network cost

• Adding Prim cost for an already visited node

• Using DSU without sorting in Kruskal

• Assuming the MST is unique

Interview Rules

Connect all nodes cheaply → MST
Edges accepted            → V − 1
Cycle                     → reject
Edge list                 → Kruskal + DSU
Adjacency list            → Prim + heap
Disconnected              → spanning forest
Shortest source route     → not MST

MST → cheapest total network
Tree edges → V − 1
No cycles → mandatory
Kruskal → edge list + DSU
Prim → adjacency + heap
Disconnected → spanning forest
MST path ≠ shortest path

💡 Golden Rule: Repeatedly choose a safe cheapest connection until every node is connected without a cycle.