Minimum Spanning Tree Prim's Algorithm in DSA Rust

Mental Model

Start from any node and keep adding the cheapest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building a road network connecting all cities with the least total cost by always choosing the shortest new road from the cities already connected.

Graph:
  (0)
 /   \
(1)---(2)

Start at node 0, tree grows by adding cheapest edges connecting new nodes.

Dry Run Walkthrough

Input: Graph with nodes 0,1,2 and edges: 0-1(4), 0-2(3), 1-2(5). Start from node 0.

Goal: Build a tree connecting all nodes with minimum total edge weight.

Step 1: Start from node 0, add it to MST set.

MST nodes: [0]
Edges considered: 0-1(4), 0-2(3)

Why: We need a starting point to begin building the MST.

Step 2: Choose edge 0-2 with weight 3 (smallest among edges from MST). Add node 2 to MST.

MST nodes: [0, 2]
Edges considered: 0-1(4), 2-1(5)

Why: Pick the cheapest edge connecting a new node to MST.

Step 3: Choose edge 0-1 with weight 4 (smaller than 2-1(5)). Add node 1 to MST.

MST nodes: [0, 2, 1]
All nodes included.

Why: Add the last node with the smallest connecting edge.

Result:

MST edges: 0-2(3) -> 0-1(4)
Total weight: 7

Annotated Code

DSA Rust

use std::collections::{BinaryHeap, HashSet};
use std::cmp::Reverse;

#[derive(Debug)]
struct Edge {
    node: usize,
    cost: usize,
}

fn prim_mst(graph: &Vec<Vec<Edge>>, start: usize) -> Vec<(usize, usize, usize)> {
    let mut mst_edges = Vec::new();
    let mut visited = HashSet::new();
    let mut heap = BinaryHeap::new();

    visited.insert(start);
    for edge in &graph[start] {
        heap.push(Reverse((edge.cost, start, edge.node)));
    }

    while let Some(Reverse((cost, from, to))) = heap.pop() {
        if visited.contains(&to) {
            continue; // skip if node already in MST
        }
        visited.insert(to);
        mst_edges.push((from, to, cost));

        for edge in &graph[to] {
            if !visited.contains(&edge.node) {
                heap.push(Reverse((edge.cost, to, edge.node)));
            }
        }
    }

    mst_edges
}

fn main() {
    // Graph adjacency list: each node has edges with cost
    // 0: (1,4), (2,3)
    // 1: (0,4), (2,5)
    // 2: (0,3), (1,5)
    let graph = vec![
        vec![Edge { node: 1, cost: 4 }, Edge { node: 2, cost: 3 }],
        vec![Edge { node: 0, cost: 4 }, Edge { node: 2, cost: 5 }],
        vec![Edge { node: 0, cost: 3 }, Edge { node: 1, cost: 5 }],
    ];

    let mst = prim_mst(&graph, 0);
    for (from, to, cost) in mst {
        println!("{} - {} : {}", from, to, cost);
    }
}

visited.insert(start);

Add starting node to MST set

for edge in &graph[start] { heap.push(Reverse((edge.cost, start, edge.node))); }

Add all edges from start node to priority queue

while let Some(Reverse((cost, from, to))) = heap.pop() {

Pick the smallest edge connecting MST to new node

if visited.contains(&to) { continue; }

Skip edges leading to nodes already in MST

visited.insert(to);

Add new node to MST

mst_edges.push((from, to, cost));

Record edge added to MST

for edge in &graph[to] { if !visited.contains(&edge.node) { heap.push(Reverse((edge.cost, to, edge.node))); } }

Add edges from new node to priority queue if they lead to unseen nodes

Output

0 - 2 : 3

0 - 1 : 4

Complexity Analysis

Time: O(E log V) because each edge is pushed and popped from the priority queue at most once, and the queue operations take log V time.

Space: O(V + E) for storing the graph and the priority queue.

vs Alternative: Compared to Kruskal's algorithm which sorts edges first (O(E log E)), Prim's can be more efficient on dense graphs using adjacency lists and priority queues.

Edge Cases

Graph with a single node and no edges

Returns empty MST since no edges exist

DSA Rust

visited.insert(start);

Disconnected graph (not all nodes reachable from start)

MST includes only connected component reachable from start

DSA Rust

while let Some(Reverse((cost, from, to))) = heap.pop() {

Graph with multiple edges of same weight

Algorithm picks edges in order of insertion but still forms valid MST

DSA Rust

if visited.contains(&to) { continue; }

When to Use This Pattern

When you need to connect all points with minimum total cost and can grow the solution from any starting point, use Prim's algorithm because it greedily adds the cheapest edge expanding the tree.

Common Mistakes

Mistake: Not checking if a node is already in MST before adding edges from it
Fix: Add a visited check before processing edges to avoid cycles and duplicates

Mistake: Using a max-heap instead of a min-heap for edge costs
Fix: Use a min-heap or invert costs with Reverse to always pick smallest edge

Summary

Builds a minimum spanning tree by adding the cheapest edge connecting new nodes to the growing tree.

Use when you want to connect all nodes with minimum total edge cost starting from any node.

Always pick the smallest edge that connects a new node to the existing MST to ensure minimal total cost.

Practice

1. What is the main goal of Prim's Algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the minimum spanning tree connecting all vertices with minimum total edge weight

C. To find the shortest path between two vertices

D. To sort vertices in topological order

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm builds a tree that connects all vertices with the smallest possible sum of edge weights.

2. Step 2: Compare with other graph algorithms

   Shortest path algorithms find paths, cycle detection finds loops, and topological sort orders vertices, which are different goals.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with minimum total edge weight -> Option B

4. Quick Check:

   Prim's Algorithm = Minimum Spanning Tree [OK]

Hint: Prim's builds minimum spanning tree by adding cheapest edges [OK]

Common Mistakes:

• Confusing Prim's with shortest path algorithms
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which Rust data structure is best suited to efficiently pick the next minimum edge in Prim's Algorithm?

easy

A. Vec (Vector)

B. LinkedList

C. HashMap

D. BinaryHeap (Min-Heap)

Solution

1. Step 1: Identify operation needed in Prim's Algorithm

   Prim's needs to repeatedly select the edge with the smallest weight efficiently.

2. Step 2: Choose data structure for minimum extraction

   A BinaryHeap (min-heap) allows quick access to the smallest element, unlike Vec or LinkedList which require scanning.

3. Final Answer:

   BinaryHeap (Min-Heap) -> Option D

4. Quick Check:

   Min-Heap = Efficient minimum edge selection [OK]

Hint: Use min-heap to get smallest edge fast in Prim's [OK]

Common Mistakes:

• Using Vec which is slow for minimum extraction
• Choosing HashMap which is for key-value, not min extraction
• Using LinkedList which is inefficient for this

3. What is the output of the following Rust code snippet implementing Prim's Algorithm on a graph with edges [(0,1,2), (1,2,3), (0,2,1)] starting from vertex 0?

let edges = vec![(0,1,2), (1,2,3), (0,2,1)];
// Prim's MST total weight calculation
// Output the total weight of MST

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: List edges and weights

   Edges: (0-1)=2, (1-2)=3, (0-2)=1. Start from vertex 0.

2. Step 2: Build MST using Prim's Algorithm

   Start at 0, pick smallest edge (0-2)=1, then pick next smallest connecting edge (0-1)=2. Total weight = 1 + 2 = 3.

3. Step 3: Check if all vertices connected

   Vertices 0,1,2 connected with edges (0-2) and (0-1). Edge (1-2) with weight 3 is not needed.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   MST weight = 1 + 2 = 3 [OK]

Hint: Pick smallest edges connecting new vertices stepwise [OK]

Common Mistakes:

• Adding all edges instead of MST edges
• Choosing heavier edges first
• Not starting from given start vertex

4. Identify the bug in this Rust snippet implementing Prim's Algorithm:

let mut visited = vec![false; n];
let mut heap = BinaryHeap::new();
heap.push(Reverse((0, 0)));
while let Some(Reverse((cost, u))) = heap.pop() {
    if visited[u] { continue; }
    visited[u] = true;
    for &(v, w) in &graph[u] {
        if !visited[v] {
            heap.push(Reverse((w, v)));
        }
    }
}

medium

A. The heap should be a max-heap, not min-heap

B. The heap should store (cost, vertex) as (u, cost) instead

C. The visited check is missing before pushing neighbors

D. The graph adjacency list should store (vertex, weight) not (weight, vertex)

Solution

1. Step 1: Analyze visited check placement

   Currently, neighbors are pushed without checking if visited, causing duplicates in heap.

2. Step 2: Fix by checking visited before pushing neighbors

   Adding a visited check before pushing neighbors avoids unnecessary heap entries and improves efficiency.

3. Final Answer:

   The visited check is missing before pushing neighbors -> Option C

4. Quick Check:

   Check visited before pushing neighbors to heap [OK]

Hint: Check visited before pushing neighbors to avoid duplicates [OK]

Common Mistakes:

• Ignoring visited check before pushing neighbors
• Confusing min-heap with max-heap
• Swapping vertex and weight in tuples

5. Given a weighted undirected graph with vertices 0 to 4 and edges:

(0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4), (3,4,2)

Using Prim's Algorithm starting from vertex 0, what is the total weight of the minimum spanning tree?

hard

A. 21

B. 17

C. 27

D. 22

Solution

1. Step 1: Start from vertex 0 and pick smallest edges stepwise

   Edges from 0: (0-3)=5, (0-2)=6, (0-1)=10. Pick (0-3)=5 first.

2. Step 2: Add edges connecting new vertices with minimum weight

   From visited {0,3}, edges: (3-4)=2, (3-2)=4, (0-2)=6, (0-1)=10. Pick (3-4)=2 next.

3. Step 3: Continue adding minimum edges connecting unvisited vertices

   Visited {0,3,4}, edges: (3-2)=4, (0-2)=6, (0-1)=10. Pick (3-2)=4 next.

4. Step 4: Add last vertex 1 with minimum edge

   Visited {0,2,3,4}, edges: (0-1)=10, (1-3)=15. Pick (0-1)=10.

5. Step 5: Calculate total weight

   Total = 5 + 2 + 4 + 10 = 21.

6. Final Answer:

   21 -> Option A

7. Quick Check:

   Sum of MST edges = 21 [OK]

Hint: Add smallest edge connecting new vertex each step [OK]

Common Mistakes:

• Choosing heavier edges before lighter ones
• Not updating visited set correctly
• Adding edges that create cycles