Minimum Spanning Tree Prim's Algorithm in DSA Rust - Execution Trace

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Find edges from MST to non-MST nodes

↓

Pick edge with smallest weight

↓

Add connected node to MST

↓

Repeat until all nodes in MST

Prim's algorithm grows the MST by adding the closest node not yet in the MST, repeating until all nodes are included.

Execution Sample

DSA Rust

let graph = vec![
  (0, 1, 2),
  (0, 3, 6),
  (1, 2, 3),
  (1, 3, 8),
  (2, 3, 5),
];

This code defines a weighted graph with edges between nodes and their weights.

Execution Table

Step	Operation	Nodes in MST	Edge Chosen	Visual State
1	Start at node 0	[0]	None	0
2	Choose smallest edge from MST to non-MST	[0,1]	(0-1, weight 2)	0 --2-- 1
3	Choose smallest edge from MST to non-MST	[0,1,2]	(1-2, weight 3)	0 --2-- 1 --3-- 2
4	Choose smallest edge from MST to non-MST	[0,1,2,3]	(2-3, weight 5)	0 --2-- 1 --3-- 2 --5-- 3
5	All nodes included	[0,1,2,3]	None	MST complete: 0--1--2--3

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
MST Nodes	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]	[0,1,2,3]
Edges Considered	[]	[(0-1,2),(0-3,6)]	[(0-3,6),(1-2,3),(1-3,8)]	[(0-3,6),(1-3,8),(2-3,5)]	[]	[]
Chosen Edge	None	(0-1,2)	(1-2,3)	(2-3,5)	None	None

Key Moments - 3 Insights

Why do we start with any node and not a specific one?

Prim's algorithm can start from any node because the MST will cover all nodes regardless of start. See Step 1 in execution_table where node 0 is chosen arbitrarily.

Why do we only consider edges connecting MST nodes to non-MST nodes?

To avoid cycles and ensure minimal total weight, we only pick edges that connect the growing MST to new nodes. This is shown in Steps 2-4 where edges chosen connect MST to new nodes.

What happens if multiple edges have the same smallest weight?

Any of the smallest edges can be chosen; Prim's algorithm does not specify tie-breaking. The execution_table shows unique smallest edges, but ties would be handled similarly.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are in MST after Step 3?

A [0,1,2,3]

B [0,1]

C [0,1,2]

D [0]

💡 Hint

Check the 'Nodes in MST' column at Step 3 in execution_table.

At which step does the algorithm add node 3 to the MST?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Edge Chosen' and 'Nodes in MST' columns in execution_table.

If the edge (1-3) had weight 4 instead of 8, which edge would be chosen at Step 4?

A (0-3, weight 6)

B (1-3, weight 4)

C (2-3, weight 5)

D (1-2, weight 3)

💡 Hint

Check the edges considered at Step 4 in variable_tracker and pick the smallest weight.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node.
- Add the smallest edge connecting MST to new node.
- Repeat until all nodes included.
- Avoid cycles by only adding edges to non-MST nodes.
- Result is a tree with minimum total edge weight.

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting from any node and repeatedly adding the smallest edge that connects the tree to a new node. The process continues until all nodes are included in the MST. At each step, only edges connecting the current MST nodes to nodes outside the MST are considered to avoid cycles. The algorithm stops when all nodes are part of the MST, ensuring the total edge weight is minimal.

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