Minimum Spanning Tree Prim's Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the printed state of the minimum spanning tree edges after running Prim's algorithm on the given graph?

DSA Rust

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn prim_mst(graph: &Vec<Vec<(usize, usize)>>) -> Vec<(usize, usize, usize)> {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut heap = BinaryHeap::new();
    let mut mst_edges = Vec::new();

    visited[0] = true;
    for &(to, weight) in &graph[0] {
        heap.push(Reverse((weight, 0, to)));
    }

    while let Some(Reverse((weight, from, to))) = heap.pop() {
        if visited[to] {
            continue;
        }
        visited[to] = true;
        mst_edges.push((from, to, weight));

        for &(next, w) in &graph[to] {
            if !visited[next] {
                heap.push(Reverse((w, to, next)));
            }
        }
    }

    mst_edges
}

fn main() {
    let graph = vec![
        vec![(1, 2), (3, 6)],
        vec![(0, 2), (2, 3), (3, 8), (4, 5)],
        vec![(1, 3), (4, 7)],
        vec![(0, 6), (1, 8), (4, 9)],
        vec![(1, 5), (2, 7), (3, 9)],
    ];

    let mst = prim_mst(&graph);
    for (from, to, weight) in mst {
        println!("{} -> {} with weight {}", from, to, weight);
    }
}

A

0 -> 1 with weight 2
1 -> 3 with weight 8
1 -> 4 with weight 5
2 -> 4 with weight 7

B

0 -> 1 with weight 2
1 -> 2 with weight 3
1 -> 4 with weight 5
0 -> 3 with weight 6

C

0 -> 3 with weight 6
1 -> 2 with weight 3
1 -> 4 with weight 5
3 -> 4 with weight 9

D

0 -> 1 with weight 2
0 -> 3 with weight 6
1 -> 4 with weight 5
2 -> 4 with weight 7

💡 Hint

Start from node 0 and always pick the smallest edge connecting to an unvisited node.

Prim's algorithm starts at node 0, picks edge 0->1 (weight 2), then from nodes 0 and 1 picks 1->2 (3), then 1->4 (5), and finally 0->3 (6). This forms the minimum spanning tree.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

Which data structure is essential for efficiently selecting the next edge with the smallest weight in Prim's algorithm?

A Binary Heap (Priority Queue)

B Stack

C Queue

D Linked List

💡 Hint

Think about how to always get the smallest edge quickly.

Prim's algorithm uses a priority queue (often implemented as a binary heap) to efficiently select the edge with the smallest weight connecting to the growing MST.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this Rust code produce when running Prim's algorithm on a graph with disconnected components?

DSA Rust

fn prim_mst(graph: &Vec<Vec<(usize, usize)>>) -> Vec<(usize, usize, usize)> {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut heap = std::collections::BinaryHeap::new();
    let mut mst_edges = Vec::new();

    visited[0] = true;
    for &(to, weight) in &graph[0] {
        heap.push(std::cmp::Reverse((weight, 0, to)));
    }

    while let Some(std::cmp::Reverse((weight, from, to))) = heap.pop() {
        if visited[to] {
            continue;
        }
        visited[to] = true;
        mst_edges.push((from, to, weight));

        for &(next, w) in &graph[to] {
            if !visited[next] {
                heap.push(std::cmp::Reverse((w, to, next)));
            }
        }
    }

    mst_edges
}

fn main() {
    let graph = vec![
        vec![(1, 1)],
        vec![(0, 1)],
        vec![(3, 2)],
        vec![(2, 2)],
    ];

    let mst = prim_mst(&graph);
    for (from, to, weight) in mst {
        println!("{} -> {} with weight {}", from, to, weight);
    }
}

A The code will enter an infinite loop.

B The code will panic with an index out of bounds error.

C The code will compile but produce incorrect MST edges including cycles.

D The code will run but return MST edges only for the connected component containing node 0.

💡 Hint

Consider what happens if the graph is not fully connected.

Prim's algorithm as implemented starts from node 0 and only visits nodes reachable from it. Disconnected components are ignored, so MST edges are only for the connected component containing node 0.

❓ Predict Output

advanced

Output of Prim's Algorithm on a Weighted Graph with Multiple Equal Edges

What is the output of the following Prim's algorithm run on this graph?

DSA Rust

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn prim_mst(graph: &Vec<Vec<(usize, usize)>>) -> Vec<(usize, usize, usize)> {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut heap = BinaryHeap::new();
    let mut mst_edges = Vec::new();

    visited[0] = true;
    for &(to, weight) in &graph[0] {
        heap.push(Reverse((weight, 0, to)));
    }

    while let Some(Reverse((weight, from, to))) = heap.pop() {
        if visited[to] {
            continue;
        }
        visited[to] = true;
        mst_edges.push((from, to, weight));

        for &(next, w) in &graph[to] {
            if !visited[next] {
                heap.push(Reverse((w, to, next)));
            }
        }
    }

    mst_edges
}

fn main() {
    let graph = vec![
        vec![(1, 1), (2, 1)],
        vec![(0, 1), (2, 2), (3, 4)],
        vec![(0, 1), (1, 2), (3, 3)],
        vec![(1, 4), (2, 3)],
    ];

    let mst = prim_mst(&graph);
    for (from, to, weight) in mst {
        println!("{} -> {} with weight {}", from, to, weight);
    }
}

A

0 -> 1 with weight 1
0 -> 2 with weight 1
2 -> 3 with weight 3

B

0 -> 2 with weight 1
2 -> 1 with weight 2
2 -> 3 with weight 3

C

0 -> 1 with weight 1
1 -> 2 with weight 2
2 -> 3 with weight 3

D

0 -> 1 with weight 1
0 -> 2 with weight 1
1 -> 3 with weight 4

💡 Hint

Edges with equal weights are chosen based on the order they appear in the heap.

Prim's algorithm picks edges with smallest weight first. From node 0, edges to 1 and 2 both have weight 1. Both are added. Then from node 2, edge to 3 with weight 3 is chosen before edge 1->3 with weight 4.

🚀 Application

expert

Number of Edges in MST for a Complete Graph

Given a complete graph with 7 nodes, how many edges will the minimum spanning tree produced by Prim's algorithm contain?

A 7

B 21

C 6

D 42

💡 Hint

Recall the property of MSTs regarding number of edges and nodes.

A minimum spanning tree for any connected graph with n nodes always has exactly n-1 edges.

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