LESSON 24 · PATTERN GUIDE

MST / Graph Greedy

Connect every vertex with minimum total edge weight while avoiding cycles.

FIRST, LEARN THE PATTERNA minimum spanning tree has V−1 edges. Kruskal sorts edges and uses DSU; Prim grows one connected tree with a priority queue.

The task asks for the cheapest way to connect all points or build a network with no need for directed paths.

How to approach it

Choose Kruskal for a global sorted edge list or Prim for expanding from a starting vertex; accept only safe minimum edges.

Watch out for

An MST is for connected undirected graphs. If the graph is disconnected, the result is a forest unless the task says otherwise.

A CLOSER EXPLANATION

An MST connects every vertex at minimum total cost without cycles. Kruskal considers edges from cheapest upward and uses DSU to reject an edge that would close a cycle. Prim instead maintains the cheapest edge leaving the growing tree.

NOW YOU TRY

Practice question

For edges A-B:1, B-C:2, A-C:4, what is the MST total weight?

EXAMPLEUndirected graph with 3 vertices.Give your answer before revealing the explanation.

Show a hint

Take the cheapest edges that connect new components.

Show an answer

3, using A-B and B-C.

CONNECT IT TO REAL LIFE

MST / Graph Greedy at work

Three office buildings need network cables. Cable costs are A–B $4, B–C $3, and A–C $10. What is the least cable cost to connect all offices?

Show one possible approach

$7, using B–C and A–B. The more expensive A–C cable would form a cycle and is unnecessary.

Practice next

Use these problem IDs to find additional practice for this pattern:

15841135116814897781102