Pattern #63

Grow an MST from one connected region using a min heap, cheapest frontier edges, visited-node cycle avoidance, parent reconstruction, and dense-graph variants.

Must Solve

15 core questions.

1. 1.Min Cost to Connect All Points
   medium
2. 2.Connecting Cities With Minimum Cost
   medium
3. 3.Minimum Spanning Tree Using Prim
   medium
4. 4.Minimum Cost to Connect All Nodes
   medium
5. 5.Optimize Water Distribution — MST Relation
   medium
6. 6.Minimum Cost Network Connection
   medium
7. 7.Minimum Cost to Connect Islands
   medium
8. 8.Prim's Algorithm with Adjacency List
   hard
9. 9.Prim's Algorithm with Matrix
   hard
10. 10.Minimum Spanning Forest
    hard
11. 11.Dense Graph MST
    hard
12. 12.Maximum Spanning Tree — Variant
    hard
13. 13.MST with Pre-Connected Nodes
    hard
14. 14.Minimum Cost Grid / Point Connection
    hard
15. 15.Compare Prim vs Kruskal
    hard

Also Important

1. 16.Second Minimum Spanning Tree — Advanced
   medium
2. 17.Critical MST Edges
   medium
3. 18.Dynamic MST — Advanced
   medium
4. 19.Euclidean / Manhattan MST Variants
   medium
5. 20.Network Design Problems
   medium

How to Think

Start from any node with edge weight 0
↓
Pop cheapest candidate edge
↓
Already visited? Skip it
↓
Add node and edge cost
↓
Push its outgoing candidate edges

Go Quick Reference — Heap Prim

pq := MinHeap{{weight: 0, node: start, parent: -1}}
visited := make([]bool, n)
cost, used := 0, 0

for pq.Len() > 0 {
    cur := heap.Pop(&pq).(Edge)
    if visited[cur.node] { continue }
    visited[cur.node] = true
    cost += cur.weight
    used++
    parent[cur.node] = cur.parent

    for _, edge := range graph[cur.node] {
        if !visited[edge.to] { heap.Push(&pq, edge) }
    }
}
if used != n { return -1 }
return cost

The initial zero weight brings the starting node into the tree without charging for a fake edge.

Prim Variants & Comparisons

Tree starts → any node at cost 0
Heap → candidate frontier edges
Visited pop → skip before cost
New node → accept edge + push neighbors
Visited count V → MST complete

Complexity

Adjacency list + heap: O(E log V) time, O(V + E) space
Adjacency matrix:      O(V²) time, O(V) extra space
Complete point graph:  O(V²) dense Prim can avoid O(V²) stored edges

Common Interview Mistakes

• Confusing Prim with Dijkstra

• Adding cost for an already visited node

• Marking a node visited when pushed instead of when selected

• Not pushing the newly selected node’s outgoing edges

• Forgetting the connectivity check

• Using directed edges for an MST

• Thinking the start node changes minimum total cost

• Assuming MST paths are source shortest paths

Interview Rules

Grow one MST        → Prim
Heap item           → (edge weight, node, parent)
Start item          → (0, start, -1)
Visited node        → skip before adding cost
New node            → add cost + push edges
Completion          → visited count == V
Dense graph         → O(V²) matrix Prim
Shortest paths      → Dijkstra, not Prim

Prim → grow one MST
Heap key → incoming edge weight
Start → cost 0
Visited pop → skip
New node → add cost
Parent → chosen MST edge
Time → O(E log V)

💡 Golden Rule: Always add the cheapest edge that crosses from the current tree to an unvisited node.