Graphs & Networks
Minimum Spanning Tree
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
connect allminimum costspanning treeKruskalPrimedges
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Must all nodes be connected with minimum total edge cost?
- Are edges undirected?
- Can sorted edges plus union find avoid cycles?
Classic problem
Minimum Spanning Tree (Kruskal) — Sort edges by weight and greedily add each edge that doesn’t form a cycle, using Union-Find. Stop when n-1 edges are accepted.
Input: edges = [["A","C",1],["C","D",2],["D","E",3],["B","E",4],["B","D",5],["A","B",6],["C","B",7]], n = 5
Output: 11 — accepted edges A–C(1), C–D(2), D–E(3), B–D(5) form the MST with total weight 11.
Common pitfalls
Applying MST to shortest-path questions.
Forgetting to verify every node became connected.