Course contentsShow
← Mathematics
Lesson 2676 of 3,12153. Graph TheoryFree lesson

Minimum Spanning Trees: Prim's Algorithm

Apply Prim's algorithm: grow the MST from a starting vertex by adding minimum-weight edges.

Minimum Spanning Trees: Prim's Algorithm

You'll learn how to build a minimum spanning tree by starting from one vertex and greedily adding the cheapest edge that connects to a new vertex.

The Core Idea

Prim's algorithm constructs a minimum spanning tree (MST) by growing it one edge at a time. Unlike Kruskal's algorithm, which considers all edges globally, Prim's algorithm works more like a spreading ink stain: you start with a single vertex, then repeatedly add the minimum-weight edge that connects your growing tree to a new, unvisited vertex.

Think of it like building a transportation network outward from a central city. At each step, you choose the cheapest road that connects a city already in your network to a new city outside it.

How Prim's Algorithm Works

  1. Initialize: Pick any starting vertex and add it to the MST.
  2. Grow: Look at all edges connecting vertices inside the MST to vertices outside the MST.
  3. Choose minimum: Select the edge with the smallest weight among those crossing the boundary.
  4. Add: Include this edge and its new vertex in the MST.
  5. Repeat: Continue until all vertices are included.

Example Walkthrough

Suppose you have vertices A, B, C, D with edges:

  • A–B: weight 2
  • A–C: weight 3
  • B–C: weight 1
  • B–D: weight 4
  • C–D: weight 2

Starting at vertex A:

  1. MST = {A}. Edges crossing: A–B(2), A–C(3). Choose A–B.
  2. MST = {A, B}. Edges crossing: B–C(1), A–C(3), B–D(4). Choose B–C.
  3. MST = {A, B, C}. Edges crossing: C–D(2), B–D(4). Choose C–D.
  4. All vertices included. MST weight = 2 + 1 + 2 = 5.

Key Takeaway: Prim's algorithm builds an MST by always adding the cheapest edge that connects a new vertex to the growing tree, ensuring optimal total weight.