Prim's Algorithm - Learning Module

Loading content...

0/276

Growing the Tree from a Vertex — Prim's Vertex-Centric Expansion

The Tree That Grows One Vertex at a Time

Picture a plant growing from a seed. It starts as a single point, then sends out roots in the most efficient direction—not too far, not too ambitious—just the nearest nutrient-rich soil. Prim's algorithm grows a minimum spanning tree in exactly this way: starting from a single vertex seed, it reaches out to the nearest unconnected vertex, integrating it into the growing structure, and repeats until the entire graph is spanned.

This vertex-centric perspective is what distinguishes Prim's algorithm from Kruskal's edge-centric approach. Understanding this growth pattern deeply is essential for implementing Prim's efficiently and debugging it when things go wrong.

What You Will Learn

By the end of this page, you will understand the vertex-by-vertex expansion strategy of Prim's algorithm, how to track which vertices are in the tree, how to identify candidate edges at each step, and the complete algorithm flow from initialization to termination.

Vertex-Centric vs Edge-Centric Thinking

There are two classical approaches to MST construction, and understanding their difference illuminates why Prim's algorithm works the way it does:

Kruskal's Algorithm (Edge-Centric):

Consider edges in order of weight
Include an edge if it doesn't create a cycle
No concept of a "growing tree"—just a forest that eventually coalesces
Requires cycle detection (Union-Find)

Prim's Algorithm (Vertex-Centric):

Maintain a single growing tree
Always expand by adding the nearest unvisited vertex
Edges are considered only if they connect to the current tree
Requires tracking vertices in/out of tree

Prim's Strengths

•Maintains a single connected tree throughout
•Natural for dense graphs (many edges)
•Easy to track parent pointers for path reconstruction
•Integrates well with priority queues
•Simpler invariant: tree is always valid MST prefix

Kruskal's Strengths

•Natural for sparse graphs (few edges)
•Can process edges in any order once sorted
•Easily parallelizable
•No starting vertex needed
•Clear edge output (list of MST edges)

Intuition Tip

Think of Prim's as growing a single organism outward, while Kruskal's builds multiple disconnected fragments that eventually fuse. Both produce the same MST, but Prim's always has exactly one connected component at each step.

The Growing Tree Invariant

To understand Prim's algorithm deeply, we must understand the invariant it maintains at every step. An invariant is a property that remains true throughout the algorithm's execution.

Prim's Core Invariant:

At all times, the current set of edges forms a tree T that:

Is connected (all vertices in T can reach each other)

Is a subset of some minimum spanning tree

Contains no cycles

This invariant is maintained because:

We start with a single vertex (trivially a tree)
We only add edges to vertices NOT in the tree (no cycles possible)
By the Cut Property, each edge we add is in some MST

Why Invariants Matter

Invariants are the key to proving algorithm correctness. If the invariant holds at the start, and each step preserves it, and the invariant plus termination condition implies our goal—then the algorithm is correct. This is inductive reasoning applied to algorithms.

Visual Model — The Frontier:

Imagine the growing tree as a region on a map. The frontier is the boundary between explored (in-tree) and unexplored (not-in-tree) vertices. At each step:

Examine all edges that cross the frontier (cut edges)
Select the minimum-weight edge
Move that edge's endpoint from unexplored to explored
The frontier expands to include new edges from the newly added vertex

This frontier expansion is the heart of Prim's algorithm.

Converting Mermaid diagram...

In the diagram, solid lines represent edges already in the tree. Dashed lines with weights are frontier edges—candidates for the next addition. The minimum frontier edge (D-E with weight 1) is NOT a candidate because D isn't in the tree yet! The actual candidates are B-D(2), C-D(3), and C-E(5). We would select B-D(2) as the minimum.

Tracking the Two Sets:

Implementing Prim's requires tracking two sets:

inTree[]: Boolean array where inTree[v] = true if vertex v is in the tree
parent[]: For each vertex, which vertex is its parent in the MST (useful for reconstruction)

Algorithm Walkthrough

Let's trace through the complete algorithm with a detailed example. We'll use a graph with 6 vertices to see the expansion pattern clearly.

Initial Graph:

Converting Mermaid diagram...

Complete Trace (Starting from vertex A):

Initialization:

Tree Vertices: {A} Tree Edges: ∅ Frontier Edges: A-B(1), A-C(4)

We start with just vertex A. The frontier consists of all edges incident to A:

A-B with weight 1
A-C with weight 4

Minimum frontier edge: A-B (weight 1)

Key Implementation Details

Transforming the conceptual algorithm into correct code requires careful attention to several implementation details:

Essential Data Structures

•inTree[v] — Boolean array. inTree[v] = true once vertex v is added to the MST. Used to skip edges leading to already-included vertices.
•key[v] — The weight of the minimum-weight edge connecting v to the current tree. Initially ∞ for all vertices except the start (which is 0).
•parent[v] — The vertex from which v was added to the tree. Allows MST reconstruction. Parent of start vertex is -1 or null.
•Graph representation — Adjacency list is preferred. For each vertex, store a list of (neighbor, weight) pairs.

The key[] Array Is Critical

The key[] array tracks the 'cost' to add each vertex to the tree. This is NOT the same as distance from the start! It's the weight of the minimum edge connecting the vertex to the current tree—and it can decrease as the tree grows and new edges become available.

Pseudocode (Naive Version — O(V²)):

prims_naive.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function PrimsNaive(graph, n, start):
    // Initialize arrays
    inTree = [false] * n
    key = [∞] * n
    parent = [-1] * n
    
    // Start vertex has key 0
    key[start] = 0
    
    // We need to add n vertices to the tree
    for i from 1 to n:
        // Find vertex with minimum key not yet in tree
        u = vertex with minimum key[u] where inTree[u] = false
        
        // Add u to the tree
        inTree[u] = true
        
        // Update keys of u's neighbors
        for each edge (u, v, weight) in graph:
            if not inTree[v] and weight < key[v]:
                key[v] = weight
                parent[v] = u
    
    // Reconstruct MST from parent array
    mstEdges = []
    for v from 0 to n-1:
        if parent[v] ≠ -1:
            mstEdges.append((parent[v], v, key[v]))
    
    return mstEdges

Why This Is O(V²):

Outer loop: V iterations (one per vertex)
Finding minimum key: O(V) scan of all vertices
Updating neighbors: O(degree) per vertex, summing to O(E) total
Total: O(V × V + E) = O(V²) for dense graphs

This is acceptable for small or dense graphs, but we can do much better using a priority queue—which we'll explore in the next page.

The Parent Array and MST Reconstruction

One of Prim's elegant features is how naturally it tracks the MST structure through the parent array. Let's understand this in detail.

What parent[v] Represents:

When we add vertex v to the tree, we're adding it via some edge (u, v). The vertex u becomes the parent of v in the MST. Setting parent[v] = u records this relationship.

From parent[] to MST Edges:

Once Prim's completes, we can reconstruct the MST:

for each vertex v (except start):
    MST contains edge (parent[v], v) with weight key[v]

From parent[] to a Tree Structure:

The parent array also defines a rooted tree with the start vertex as root:

start has no parent (parent[start] = -1)
Every other vertex v has parent[v] pointing towards the root
This is useful for path queries in the MST

Parent Array for Our Example (starting from A)
Vertex	parent[v]	key[v]	MST Edge Added
A (start)	-1	0	—
B	A	1	A — B
C	B	2	B — C
D	C	3	C — D
E	C	5	C — E
F	D	8	D — F

Parent Array Visualization

If you draw arrows from each vertex to its parent, you get a tree rooted at the starting vertex. This tree structure is exactly the MST! The arrows point 'inward' toward the root, showing how each vertex joined the growing tree.

Path to Root Query:

Using the parent array, we can find the path from any vertex to the root:

function pathToRoot(parent[], v):
    path = []
    while v ≠ -1:
        path.append(v)
        v = parent[v]
    return path

For vertex F in our example: F → D → C → B → A

Why This Matters:

The parent structure is useful for:

Verifying the MST is correctly constructed
Answering path queries in the MST
Visualizing and debugging the algorithm
Converting to other MST representations (edge list, adjacency list)

Handling Edge Cases

A robust implementation must handle several edge cases correctly:

Edge Cases to Consider

•Disconnected Graph — Prim's can only span vertices reachable from the start. If the graph is disconnected, it produces a spanning tree of the connected component containing the start vertex, not a spanning forest. Detection: after n iterations, some inTree[v] remains false.
•Single Vertex Graph — Trivially, the MST is empty (no edges needed). The algorithm correctly terminates after the first iteration with an empty edge list.
•No Edges Graph — Each vertex is its own component. Prim's visits only the start vertex and terminates with no edges. Not an MST of the graph, just the starting vertex.
•Equal Weight Edges — Multiple valid MSTs may exist. Prim's produces one of them. The specific MST depends on tie-breaking (which can be arbitrary or deterministic based on vertex IDs).
•Self-Loops — Edges from a vertex to itself. These are never useful for spanning trees and should be ignored (they'd create a cycle of length 1).
•Parallel Edges (Multigraph) — Multiple edges between the same pair of vertices. Only the minimum-weight edge between any pair matters. Can be handled during graph construction or during the algorithm.

Detecting Disconnected Graphs

If your algorithm terminates but some vertices have key[v] = ∞, the graph was disconnected. You can either report an error or run Prim's again from an unvisited vertex to find a spanning forest.

disconnected_check.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function PrimsWithDisconnectedCheck(graph, n, start):
    // Run standard Prim's...
    (inTree, key, parent) = PrimsCore(graph, n, start)
    
    // Check for disconnected vertices
    disconnected = []
    for v from 0 to n-1:
        if not inTree[v]:
            disconnected.append(v)
    
    if len(disconnected) > 0:
        print("Warning: Graph is disconnected!")
        print("Unreachable vertices:", disconnected)
        return (MST of connected component, disconnected)
    
    return (MST, [])

Comparing Growth Orders

An interesting property of Prim's algorithm is that different starting vertices produce different growth orders but the same final MST (for graphs with distinct edge weights). Let's explore this:

Different Starting Vertices, Same MST
Start	Addition Order	Final MST Edges	Total Weight
A	A → B → C → D → E → F	{A-B, B-C, C-D, C-E, D-F}	19
C	C → B → A → D → E → F	{B-C, A-B, C-D, C-E, D-F}	19
F	F → D → C → B → A → E	{D-F, C-D, B-C, A-B, C-E}	19

Observation: The vertices are added in different orders, but the same edges appear in the final MST every time. This confirms that:

The MST is unique (when edge weights are distinct)
Starting vertex doesn't affect the result
The greedy property guarantees we find the same optimal structure

When Does Order Matter?

While the final MST is the same, the growth order affects:

Intermediate states: The frontier edges differ at each step
Priority queue operations: Different edges are inserted/extracted
Debugging complexity: Some orders may be easier to trace manually
Tie-breaking sensitivity: With equal weights, different starts may produce different MSTs of equal total weight

Practical Implication

In practice, choosing a good starting vertex doesn't affect correctness or asymptotic complexity. However, for visualization or debugging purposes, starting from a vertex with low-degree edges can make manual tracing simpler.

Summary: Growing the Tree from a Vertex

We've deeply explored the mechanics of Prim's vertex-by-vertex tree growth:

Key Takeaways

•Prim's is vertex-centric — Unlike Kruskal's edge-based approach, Prim's maintains a single connected tree that grows one vertex at a time.
•The frontier separates explored from unexplored — At each step, we examine edges crossing from in-tree to not-in-tree vertices.
•The invariant maintains correctness — The current tree is always a subset of some MST, guaranteed by the Cut Property.
•Three arrays track state — inTree[] marks membership, key[] tracks minimum connection cost, parent[] records the MST structure.
•Naive implementation is O(V²) — Finding the minimum key vertex via linear scan is the bottleneck in the simple version.
•Edge cases require careful handling — Disconnected graphs, self-loops, and equal weights need explicit consideration.

What's Next:

The naive O(V²) implementation is impractical for large graphs. The next page introduces the priority queue optimization that reduces the complexity to O((V + E) log V)—making Prim's algorithm efficient enough for real-world network design, routing applications, and massive infrastructure planning.

Page Complete

You now understand how Prim's algorithm grows an MST vertex by vertex, the data structures required, and the invariant that guarantees correctness. Next, we'll optimize this approach using priority queues for logarithmic-time minimum extraction.

Growing the Tree from a Vertex — Prim's Vertex-Centric Expansion

The Tree That Grows One Vertex at a Time

What You Will Learn

Vertex-Centric vs Edge-Centric Thinking

There are two classical approaches to MST construction, and understanding their difference illuminates why Prim's algorithm works the way it does:

Kruskal's Algorithm (Edge-Centric):

Consider edges in order of weight
Include an edge if it doesn't create a cycle
No concept of a "growing tree"—just a forest that eventually coalesces
Requires cycle detection (Union-Find)

Prim's Algorithm (Vertex-Centric):

Maintain a single growing tree
Always expand by adding the nearest unvisited vertex
Edges are considered only if they connect to the current tree
Requires tracking vertices in/out of tree

Prim's Strengths

•Maintains a single connected tree throughout
•Natural for dense graphs (many edges)
•Easy to track parent pointers for path reconstruction
•Integrates well with priority queues
•Simpler invariant: tree is always valid MST prefix

Kruskal's Strengths

•Natural for sparse graphs (few edges)
•Can process edges in any order once sorted
•Easily parallelizable
•No starting vertex needed
•Clear edge output (list of MST edges)

Intuition Tip

The Growing Tree Invariant

To understand Prim's algorithm deeply, we must understand the invariant it maintains at every step. An invariant is a property that remains true throughout the algorithm's execution.

Prim's Core Invariant:

At all times, the current set of edges forms a tree T that:

Is connected (all vertices in T can reach each other)

Is a subset of some minimum spanning tree

Contains no cycles

This invariant is maintained because:

We start with a single vertex (trivially a tree)
We only add edges to vertices NOT in the tree (no cycles possible)
By the Cut Property, each edge we add is in some MST

Why Invariants Matter

Visual Model — The Frontier:

Imagine the growing tree as a region on a map. The frontier is the boundary between explored (in-tree) and unexplored (not-in-tree) vertices. At each step:

Examine all edges that cross the frontier (cut edges)
Select the minimum-weight edge
Move that edge's endpoint from unexplored to explored
The frontier expands to include new edges from the newly added vertex

This frontier expansion is the heart of Prim's algorithm.

Converting Mermaid diagram...

Tracking the Two Sets:

Implementing Prim's requires tracking two sets:

inTree[]: Boolean array where inTree[v] = true if vertex v is in the tree
parent[]: For each vertex, which vertex is its parent in the MST (useful for reconstruction)

Algorithm Walkthrough

Let's trace through the complete algorithm with a detailed example. We'll use a graph with 6 vertices to see the expansion pattern clearly.

Initial Graph:

Converting Mermaid diagram...

Complete Trace (Starting from vertex A):

Initialization:

Tree Vertices: {A} Tree Edges: ∅ Frontier Edges: A-B(1), A-C(4)

We start with just vertex A. The frontier consists of all edges incident to A:

A-B with weight 1
A-C with weight 4

Minimum frontier edge: A-B (weight 1)

Key Implementation Details

Transforming the conceptual algorithm into correct code requires careful attention to several implementation details:

Essential Data Structures

•inTree[v] — Boolean array. inTree[v] = true once vertex v is added to the MST. Used to skip edges leading to already-included vertices.
•key[v] — The weight of the minimum-weight edge connecting v to the current tree. Initially ∞ for all vertices except the start (which is 0).
•parent[v] — The vertex from which v was added to the tree. Allows MST reconstruction. Parent of start vertex is -1 or null.
•Graph representation — Adjacency list is preferred. For each vertex, store a list of (neighbor, weight) pairs.

The key[] Array Is Critical

Pseudocode (Naive Version — O(V²)):

prims_naive.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function PrimsNaive(graph, n, start):
    // Initialize arrays
    inTree = [false] * n
    key = [∞] * n
    parent = [-1] * n
    
    // Start vertex has key 0
    key[start] = 0
    
    // We need to add n vertices to the tree
    for i from 1 to n:
        // Find vertex with minimum key not yet in tree
        u = vertex with minimum key[u] where inTree[u] = false
        
        // Add u to the tree
        inTree[u] = true
        
        // Update keys of u's neighbors
        for each edge (u, v, weight) in graph:
            if not inTree[v] and weight < key[v]:
                key[v] = weight
                parent[v] = u
    
    // Reconstruct MST from parent array
    mstEdges = []
    for v from 0 to n-1:
        if parent[v] ≠ -1:
            mstEdges.append((parent[v], v, key[v]))
    
    return mstEdges

Why This Is O(V²):

Outer loop: V iterations (one per vertex)
Finding minimum key: O(V) scan of all vertices
Updating neighbors: O(degree) per vertex, summing to O(E) total
Total: O(V × V + E) = O(V²) for dense graphs

This is acceptable for small or dense graphs, but we can do much better using a priority queue—which we'll explore in the next page.

The Parent Array and MST Reconstruction

One of Prim's elegant features is how naturally it tracks the MST structure through the parent array. Let's understand this in detail.

What parent[v] Represents:

When we add vertex v to the tree, we're adding it via some edge (u, v). The vertex u becomes the parent of v in the MST. Setting parent[v] = u records this relationship.

From parent[] to MST Edges:

Once Prim's completes, we can reconstruct the MST:

for each vertex v (except start):
    MST contains edge (parent[v], v) with weight key[v]

From parent[] to a Tree Structure:

The parent array also defines a rooted tree with the start vertex as root:

start has no parent (parent[start] = -1)
Every other vertex v has parent[v] pointing towards the root
This is useful for path queries in the MST

Parent Array for Our Example (starting from A)
Vertex	parent[v]	key[v]	MST Edge Added
A (start)	-1	0	—
B	A	1	A — B
C	B	2	B — C
D	C	3	C — D
E	C	5	C — E
F	D	8	D — F

Parent Array Visualization

Path to Root Query:

Using the parent array, we can find the path from any vertex to the root:

function pathToRoot(parent[], v):
    path = []
    while v ≠ -1:
        path.append(v)
        v = parent[v]
    return path

For vertex F in our example: F → D → C → B → A

Why This Matters:

The parent structure is useful for:

Verifying the MST is correctly constructed
Answering path queries in the MST
Visualizing and debugging the algorithm
Converting to other MST representations (edge list, adjacency list)

Handling Edge Cases

A robust implementation must handle several edge cases correctly:

Edge Cases to Consider

•Disconnected Graph — Prim's can only span vertices reachable from the start. If the graph is disconnected, it produces a spanning tree of the connected component containing the start vertex, not a spanning forest. Detection: after n iterations, some inTree[v] remains false.
•Single Vertex Graph — Trivially, the MST is empty (no edges needed). The algorithm correctly terminates after the first iteration with an empty edge list.
•No Edges Graph — Each vertex is its own component. Prim's visits only the start vertex and terminates with no edges. Not an MST of the graph, just the starting vertex.
•Equal Weight Edges — Multiple valid MSTs may exist. Prim's produces one of them. The specific MST depends on tie-breaking (which can be arbitrary or deterministic based on vertex IDs).
•Self-Loops — Edges from a vertex to itself. These are never useful for spanning trees and should be ignored (they'd create a cycle of length 1).
•Parallel Edges (Multigraph) — Multiple edges between the same pair of vertices. Only the minimum-weight edge between any pair matters. Can be handled during graph construction or during the algorithm.

Detecting Disconnected Graphs

If your algorithm terminates but some vertices have key[v] = ∞, the graph was disconnected. You can either report an error or run Prim's again from an unvisited vertex to find a spanning forest.

disconnected_check.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function PrimsWithDisconnectedCheck(graph, n, start):
    // Run standard Prim's...
    (inTree, key, parent) = PrimsCore(graph, n, start)
    
    // Check for disconnected vertices
    disconnected = []
    for v from 0 to n-1:
        if not inTree[v]:
            disconnected.append(v)
    
    if len(disconnected) > 0:
        print("Warning: Graph is disconnected!")
        print("Unreachable vertices:", disconnected)
        return (MST of connected component, disconnected)
    
    return (MST, [])

Comparing Growth Orders

An interesting property of Prim's algorithm is that different starting vertices produce different growth orders but the same final MST (for graphs with distinct edge weights). Let's explore this:

Different Starting Vertices, Same MST
Start	Addition Order	Final MST Edges	Total Weight
A	A → B → C → D → E → F	{A-B, B-C, C-D, C-E, D-F}	19
C	C → B → A → D → E → F	{B-C, A-B, C-D, C-E, D-F}	19
F	F → D → C → B → A → E	{D-F, C-D, B-C, A-B, C-E}	19

Observation: The vertices are added in different orders, but the same edges appear in the final MST every time. This confirms that:

The MST is unique (when edge weights are distinct)
Starting vertex doesn't affect the result
The greedy property guarantees we find the same optimal structure

When Does Order Matter?

While the final MST is the same, the growth order affects:

Intermediate states: The frontier edges differ at each step
Priority queue operations: Different edges are inserted/extracted
Debugging complexity: Some orders may be easier to trace manually
Tie-breaking sensitivity: With equal weights, different starts may produce different MSTs of equal total weight

Practical Implication

Summary: Growing the Tree from a Vertex

We've deeply explored the mechanics of Prim's vertex-by-vertex tree growth:

Key Takeaways

•Prim's is vertex-centric — Unlike Kruskal's edge-based approach, Prim's maintains a single connected tree that grows one vertex at a time.
•The frontier separates explored from unexplored — At each step, we examine edges crossing from in-tree to not-in-tree vertices.
•The invariant maintains correctness — The current tree is always a subset of some MST, guaranteed by the Cut Property.
•Three arrays track state — inTree[] marks membership, key[] tracks minimum connection cost, parent[] records the MST structure.
•Naive implementation is O(V²) — Finding the minimum key vertex via linear scan is the bottleneck in the simple version.
•Edge cases require careful handling — Disconnected graphs, self-loops, and equal weights need explicit consideration.

What's Next:

Page Complete