Shortest Path in Unweighted Graph Using BFS in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a queue for BFS traversal.

DSA Rust

let mut queue = std::collections::VecDeque::new();
queue.[1](start_node);

Drag options to blanks, or click blank then click option'

Apush_front

Bpush_back

Cpop_back

Dpop_front

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop methods instead of push to add elements.

We use push_back to add the start node at the end of the queue for BFS.

2fill in blank

medium

Complete the code to get the current node from the front of the queue.

DSA Rust

while let Some(current) = queue.[1]() {
    // process current node
}

Drag options to blanks, or click blank then click option'

Apop_front

Bpush_back

Cpush_front

Dpop_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop_back which removes from the end, not front.

We use pop_front to remove and get the node at the front of the queue in BFS.

3fill in blank

hard

Fix the error in the code to mark neighbors as visited and update their distance.

DSA Rust

for &neighbor in graph[[1]].iter() {
    if !visited[neighbor] {
        visited[neighbor] = true;
        distance[neighbor] = distance[current] + 1;
        queue.push_back(neighbor);
    }
}

Drag options to blanks, or click blank then click option'

Astart_node

Bneighbor

Ccurrent

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using neighbor as index causes wrong access or panic.

We access neighbors of the current node, so the index must be current.

4fill in blank

hard

Fill both blanks to initialize the distance vector and visited vector correctly.

DSA Rust

let mut distance = vec![[1]; n];
let mut visited = vec![[2]; n];

Drag options to blanks, or click blank then click option'

Ausize::MAX

Bfalse

Ctrue

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting visited to true initially.

Setting distance to 0 initially.

Distance is set to max value to represent infinity, visited is false initially.

5fill in blank

hard

Fill all three blanks to set the start node distance, mark it visited, and push it to the queue.

DSA Rust

distance[[1]] = [2];
visited[[3]] = true;
queue.push_back(start_node);

Drag options to blanks, or click blank then click option'

Astart_node

B0

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using current instead of start_node for visited or distance.

Start node distance is 0, mark start node visited, and add start node to queue.

Practice

1. What does BFS (Breadth-First Search) find in an unweighted graph when used from a start node?

easy

A. A random path to any node

B. The longest path in the graph

C. The path with the maximum sum of edge weights

D. The shortest path in terms of number of edges to all reachable nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level, starting from the source node, visiting all neighbors before moving deeper.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance (edges), it finds the shortest path in terms of edge count.

3. Final Answer:

   The shortest path in terms of number of edges to all reachable nodes -> Option D

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS finds shortest paths by layers in unweighted graphs [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest paths
• Assuming BFS works for weighted graphs without modification

2. Which Rust code snippet correctly initializes a queue for BFS traversal?

easy

A. let queue = Vec::new();

B. let mut queue = std::collections::VecDeque::new();

C. let mut queue = std::collections::HashMap::new();

D. let mut queue = std::collections::BinaryHeap::new();

Solution

1. Step 1: Identify the correct queue type for BFS

   BFS requires a FIFO queue; VecDeque in Rust supports efficient push/pop from both ends.

2. Step 2: Check each option's suitability

   let mut queue = std::collections::VecDeque::new(); uses VecDeque which is correct; Vec (A) is not efficient as a queue; HashMap (C) is a map, not a queue; BinaryHeap (D) is a priority queue, not FIFO.

3. Final Answer:

   let mut queue = std::collections::VecDeque::new(); -> Option B

4. Quick Check:

   VecDeque = correct BFS queue [OK]

Hint: Use VecDeque for BFS queue in Rust [OK]

Common Mistakes:

• Using Vec instead of VecDeque for queue
• Using HashMap or BinaryHeap incorrectly
• Not mutably declaring the queue

3. Given the following Rust code snippet for BFS on an unweighted graph, what is the output distance vector?

let graph = vec![
    vec![1, 2],
    vec![0, 3],
    vec![0, 3],
    vec![1, 2, 4],
    vec![3]
];
let start = 0;
let mut dist = vec![-1; 5];
dist[start] = 0;
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. 0, 1, 1, 2, 3

B. 0, 1, 2, 1, 2

C. 0, 1, 1, 1, 2

D. 0, 2, 2, 3, 4

Solution

1. Step 1: Trace BFS distances from start node 0

   Start at node 0 (distance 0). Neighbors 1 and 2 get distance 1. Then from 1 and 2, node 3 gets distance 2. From 3, node 4 gets distance 3.

2. Step 2: Confirm final distance vector

   Distances: node0=0, node1=1, node2=1, node3=2, node4=3.

3. Final Answer:

   0, 1, 1, 2, 3 -> Option A

4. Quick Check:

   BFS distances = [0,1,1,2,3] [OK]

Hint: Track BFS levels to assign distances [OK]

Common Mistakes:

• Mixing up node indices and distances
• Assigning wrong distances to nodes visited later
• Forgetting to initialize distances with -1

4. Identify the bug in this BFS Rust code snippet that causes it to panic or produce incorrect distances:

let graph = vec![vec![1], vec![0, 2], vec![1]];
let start = 0;
let mut dist = vec![0; 3];
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == 0 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. Loop condition is incorrect

B. Queue is not mutable

C. Distance vector initialized with zeros causes confusion with unvisited nodes

D. Graph adjacency list is empty

Solution

1. Step 1: Check distance vector initialization

   Distances initialized to 0 means unvisited nodes and start node share same value, causing logic errors.

2. Step 2: Explain impact on BFS logic

   Condition 'if dist[v] == 0' fails to distinguish unvisited nodes, so some nodes never get updated or cause infinite loops.

3. Final Answer:

   Distance vector initialized with zeros causes confusion with unvisited nodes -> Option C

4. Quick Check:

   Use -1 for unvisited distances [OK]

Hint: Initialize distances with -1 to mark unvisited [OK]

Common Mistakes:

• Using 0 as initial distance for all nodes
• Not marking start node distance before BFS
• Ignoring mutability of queue

5. You want to find the shortest path length from node 0 to node 5 in this unweighted graph using BFS. The graph edges are:

0 - 1, 0 - 2, 1 - 3, 2 - 3, 3 - 4, 4 - 5

Which BFS distance array after traversal correctly shows the shortest distance to each node from 0? Assume nodes are 0 to 5 and unreachable nodes have distance -1.

hard

A. [0, 1, 1, 2, 3, 4]

B. [0, 1, 2, 3, 4, 5]

C. [0, 1, 1, 1, 2, 3]

D. [0, -1, -1, -1, -1, -1]

Solution

1. Step 1: Map shortest paths from node 0

   From 0: nodes 1 and 2 are 1 edge away; node 3 is 2 edges away (via 1 or 2); node 4 is 3 edges away; node 5 is 4 edges away.

2. Step 2: Confirm distances array

   Distances: 0=0, 1=1, 2=1, 3=2, 4=3, 5=4 matches [0, 1, 1, 2, 3, 4].

3. Final Answer:

   [0, 1, 1, 2, 3, 4] -> Option A

4. Quick Check:

   Shortest path distances = [0,1,1,2,3,4] [OK]

Hint: Count edges from start node to each node [OK]

Common Mistakes:

• Counting nodes instead of edges
• Mislabeling unreachable nodes
• Confusing path length with node values