CodeWithYash

Intermediate · Module 17 · Lesson 8

Minimum spanning tree

Kruskal and Prim for cheapest connectivity.

15–25 min readLesson 102 of 123

Lesson 102 of 123

1d streak

Theory lesson · Step-by-step

Understand Minimum spanning tree

Kruskal and Prim for cheapest connectivity.

Worked approach

Trace the reasoning step by step

  1. 1Sort edges for Kruskal or seed a frontier for Prim.
  2. 2Choose the cheapest safe edge.
  3. 3Join the new component or vertex.
  4. 4Stop after V−1 chosen edges.

Concrete example

Connect triangle edges AB=1, BC=2, AC=4.

  1. 1Kruskal chooses AB.
  2. 2Choose BC; all vertices connect.
  3. 3Skip AC because it creates a cycle.

MST cost is 3.

What must remain true (Loop Invariant)

The chosen edges remain extendable to a minimum spanning tree; Kruskal never adds a cycle.

Cost Model

Complexity & Trade-offs

Graph processing
O(E log E)
O(V + E)
Assumes adjacency-list representation unless stated otherwise.

When to use it

  • Networks, dependencies, connectivity, shortest paths, and grid movement.
  • Ordering prerequisite-constrained work.
  • Grouping reachable or mutually reachable states.

Common mistakes

  • Marking visited too late and enqueuing the same vertex repeatedly.
  • Ignoring disconnected components.
  • Using an algorithm whose weight assumptions do not match the graph.

Practice prompts

  • Reproduce the worked Minimum spanning tree example without looking at the trace.
  • Change one input condition and explain whether the Minimum spanning tree invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.