Course contentsShow
← Computer Science
Lesson 1017 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Prim's Algorithm: Overview

Understand Prim's greedy approach to growing an MST from a starting vertex by adding minimum-weight edges to the tree.

Prim's Algorithm: Overview

What You'll Learn

You'll learn how Prim's algorithm builds a minimum spanning tree by greedily growing it one edge at a time from a starting vertex.

The Core Idea

Prim's algorithm takes a completely different approach from Kruskal's. Instead of sorting all edges globally and merging components, Prim's grows a single tree continuously from a starting vertex.

Think of it like growing a crystal from a seed: you start with one vertex, then repeatedly attach the cheapest edge that connects your growing tree to a new vertex outside the tree. At each step, you're asking: "Of all edges touching my current tree, which one has the smallest weight and leads to an unvisited vertex?"

How It Works

  1. Start with any vertex as your initial tree (containing just that one vertex)
  2. Repeat until all vertices are in the tree:
    • Look at all edges connecting the tree to vertices not yet in the tree
    • Pick the edge with minimum weight
    • Add that edge and its new vertex to the tree

This greedy choice is always safe because of the cut property you learned earlier: the minimum-weight edge crossing a cut (between tree vertices and non-tree vertices) must be in some MST.

Analogy

Imagine building a subway system starting from city hall. Each day, you extend rails to the nearest unconnected city using the cheapest available route from your existing network. You never jump to a disconnected city—you always grow continuously.

Key Takeaway: Prim's algorithm grows a single MST from a starting vertex by repeatedly adding the minimum-weight edge that connects the tree to a new vertex, relying on the cut property for correctness.