Minimum Spanning Tree (Prim's/Kruskal's)

The Minimum Spanning Tree (Prim's/Kruskal's) technique is applied when tackling problems characterized by specific invariants in the problem state or constraints:

• Core Strategy: Build a minimum-weight tree connecting all nodes, either by growing from a frontier (Prim's) or sorting edges and using union-find (Kruskal's).
• When to use: Look for opportunities where repeated re-computation can be replaced by maintaining monotonic properties, state windows, or relational pointers.
• Interview Signal: Demonstrating this pattern shows mastery of Graphs foundations, reducing worst-case algorithmic complexity.