BFS Breadth First Search on Graph in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for and what is its main purpose in graph traversal?

BFS stands for Breadth First Search. It is used to explore all nodes of a graph layer by layer, starting from a source node and visiting all neighbors before moving to the next level.

beginner

In BFS, which data structure is primarily used to keep track of nodes to visit next?

A queue is used in BFS to keep track of nodes to visit next. It ensures nodes are processed in the order they are discovered, supporting level-by-level traversal.

intermediate

What is the time complexity of BFS on a graph with V vertices and E edges?

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and edge is processed at most once.

beginner

How does BFS ensure that it does not visit the same node multiple times?

BFS uses a 'visited' set or array to mark nodes that have already been explored. Before adding a node to the queue, it checks if the node is already visited to avoid repetition.

intermediate

What is the difference between BFS and DFS in graph traversal?

BFS explores nodes level by level using a queue, visiting all neighbors before going deeper. DFS explores as far as possible along one branch before backtracking, using a stack or recursion.

Which data structure does BFS use to keep track of nodes to visit next?

A Linked List

B Stack

C HashMap

D Queue

BFS uses a queue to process nodes in the order they are discovered, ensuring level-by-level traversal.

What is the first step in BFS starting from a source node?

A Remove the source node from the graph

B Add the source node to the queue and mark it visited

C Mark all nodes as visited

D Add all neighbors of the source node to the queue

BFS starts by adding the source node to the queue and marking it visited to begin traversal.

What does BFS guarantee when searching in an unweighted graph?

A Shortest path in terms of number of edges

B Longest path in the graph

C Random path to a node

D No path found

BFS finds the shortest path in terms of edges from the source to any reachable node in an unweighted graph.

How does BFS avoid infinite loops in graphs with cycles?

A By using recursion

B By removing edges

C By marking nodes as visited before adding them to the queue

D By sorting nodes

BFS marks nodes as visited before adding them to the queue to prevent revisiting and infinite loops.

What is the order of node visits in BFS?

A Level by level from the source node

B Random order

C Deepest nodes first

D Alphabetical order

BFS visits nodes level by level starting from the source node.

Explain how BFS works step-by-step on a graph starting from a given node.

Think about how BFS explores neighbors layer by layer.

Describe how BFS can be used to find the shortest path in an unweighted graph.

Remember BFS visits nodes by levels, so the first time you reach a node is the shortest path.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A hash map

B. A stack data structure

C. A priority queue

D. A queue data structure

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To achieve level order traversal, BFS uses a queue to process nodes in the order they are discovered.

3. Final Answer:

   A queue data structure -> Option D

4. Quick Check:

   BFS uses queue = C [OK]

Hint: BFS uses queue to explore neighbors level-wise [OK]

Common Mistakes:

• Confusing BFS with DFS which uses stack
• Thinking BFS uses priority queue
• Assuming BFS uses hash map for traversal order

2. Which of the following Rust code snippets correctly initializes a queue for BFS traversal using the standard library?

easy

A. let mut queue = HashMap::new();

B. let mut queue = Vec::new();

C. let mut queue = VecDeque::new();

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

Solution

1. Step 1: Identify the correct queue type in Rust

   Rust's standard library provides VecDeque for efficient queue operations (push_back, pop_front).

2. Step 2: Check each option

   let mut queue = VecDeque::new(); uses VecDeque::new(), which is correct. Vec is a dynamic array, not ideal for queue. HashMap and BinaryHeap are not queues.

3. Final Answer:

   let mut queue = VecDeque::new(); -> Option C

4. Quick Check:

   VecDeque is queue in Rust [OK]

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

Common Mistakes:

• Using Vec which is not efficient for queue
• Using HashMap which is for key-value pairs
• Using BinaryHeap which is a priority queue

3. Given the following Rust code for BFS on a graph represented as adjacency list, what is the order of nodes visited starting from node 0?

use std::collections::VecDeque;

fn bfs(graph: &Vec, start: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    order
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 3],
        vec![0, 4],
        vec![1],
        vec![2]
    ];
    let result = bfs(&graph, 0);
    println!("{:?}", result);
}

medium

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

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

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

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

Solution

1. Step 1: Start BFS from node 0

   Visit node 0, enqueue neighbors 1 and 2.

2. Step 2: Visit nodes in queue order

   Dequeue 1, visit it, enqueue neighbor 3 (0 already visited). Dequeue 2, visit it, enqueue neighbor 4.

3. Step 3: Continue visiting remaining nodes

   Dequeue 3, visit it (neighbor 1 visited). Dequeue 4, visit it (neighbor 2 visited).

4. Final Answer:

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

5. Quick Check:

   BFS order from 0 = [0,1,2,3,4] [OK]

Hint: BFS visits neighbors level-wise in order discovered [OK]

Common Mistakes:

• Mixing BFS with DFS order
• Visiting neighbors out of order
• Forgetting to mark visited nodes

4. The following Rust BFS code has a bug causing it to panic at runtime. What is the error?

use std::collections::VecDeque;

fn bfs(graph: &Vec, start: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                queue.push_back(neighbor);
            }
        }
    }
    order
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 3],
        vec![0, 4],
        vec![1],
        vec![2]
    ];
    let result = bfs(&graph, 0);
    println!("{:?}", result);
}

medium

A. Missing visited[neighbor] = true; causes infinite loop

B. Queue is not initialized properly

C. Graph adjacency list is empty

D. Start node index is out of bounds

Solution

1. Step 1: Analyze BFS loop and visited marking

   The code pushes neighbors to queue but never marks them visited.

2. Step 2: Understand consequence of missing visited update

   Without marking visited, neighbors get re-added repeatedly causing infinite loop or panic.

3. Final Answer:

   Missing visited[neighbor] = true; causes infinite loop -> Option A

4. Quick Check:

   Mark visited before enqueue = prevent infinite loop [OK]

Hint: Always mark visited before enqueueing neighbors [OK]

Common Mistakes:

• Forgetting to mark nodes visited before enqueue
• Assuming queue initialization causes panic
• Ignoring start node validity

5. You want to find the shortest path length from node 0 to node 4 in an unweighted graph using BFS. Which modification to the BFS code below will correctly compute the shortest distance?

use std::collections::VecDeque;

fn shortest_path_length(graph: &Vec, start: usize, target: usize) -> Option<usize> {
    let mut visited = vec![false; graph.len()];
    let mut distance = vec![0; graph.len()];
    let mut queue = VecDeque::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        if node == target {
            return Some(distance[node]);
        }
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
                // What to add here?
            }
        }
    }
    None
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 3],
        vec![0, 4],
        vec![1],
        vec![2]
    ];
    let result = shortest_path_length(&graph, 0, 4);
    println!("{:?}", result);
}

hard

A. distance[neighbor] = 1;

B. distance[neighbor] = distance[node] + 1;

C. distance[neighbor] += 1;

D. distance[neighbor] = distance[node];

Solution

1. Step 1: Understand BFS distance tracking

   Distance to neighbor is distance to current node plus one edge.

2. Step 2: Choose correct distance update

   Assign distance[neighbor] = distance[node] + 1 to track shortest path length.

3. Final Answer:

   distance[neighbor] = distance[node] + 1; -> Option B

4. Quick Check:

   Distance increments by 1 per edge [OK]

Hint: Set neighbor distance = current node distance + 1 [OK]

Common Mistakes:

• Not updating distance correctly
• Using += 1 without initialization
• Setting distance to constant 1 always