Connected Components Using BFS in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a connected component in a graph?

A connected component is a group of nodes in a graph where each node is reachable from any other node in the same group by following edges.

beginner

What does BFS stand for and what is its role in finding connected components?

BFS stands for Breadth-First Search. It explores nodes level by level and helps find all nodes connected to a starting node, identifying one connected component at a time.

beginner

In BFS for connected components, why do we mark nodes as visited?

Marking nodes as visited prevents revisiting the same node multiple times, avoiding infinite loops and ensuring each connected component is counted once.

intermediate

What is the time complexity of finding connected components using BFS in a graph with V vertices and E edges?

The time complexity is O(V + E) because BFS visits every vertex and edge once during traversal.

intermediate

How does BFS differ from DFS when finding connected components?

BFS explores neighbors level by level using a queue, while DFS explores as deep as possible along one path using a stack or recursion. Both can find connected components but differ in traversal order.

What data structure is commonly used in BFS to keep track of nodes to visit next?

A Linked List

B Stack

C HashMap

D Queue

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

What does marking a node as visited in BFS help prevent?

A Revisiting nodes and infinite loops

B Adding nodes to the queue

C Finding connected components

D Sorting nodes

Marking nodes as visited prevents revisiting the same node multiple times, which could cause infinite loops.

In a graph with 5 connected components, how many times will BFS be initiated to find all components?

A 5

B 1

C Number of edges

D Number of vertices

BFS starts once for each connected component to explore all nodes in that component.

Which of these is NOT true about BFS in connected components?

A It uses a queue

B It finds all nodes connected to a start node

C It uses recursion by default

D It marks nodes as visited

BFS typically uses a queue and iterative approach, not recursion (which is common in DFS).

What is the main goal of using BFS in connected components?

A To find the shortest path between two nodes

B To find all nodes in one connected component

C To sort nodes by value

D To delete nodes

BFS helps find all nodes reachable from a starting node, identifying one connected component.

Explain how BFS can be used to find connected components in an undirected graph.

Think about visiting all nodes reachable from a start node before moving to the next.

Describe the role of the visited set in BFS when finding connected components.

Why do we need to remember which nodes we already saw?

Practice

1. What does the BFS algorithm help find in an undirected graph when used for connected components?

easy

A. All nodes reachable from a starting node forming one connected component

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS in context of connected components

   BFS explores all nodes reachable from a starting node, grouping them as one connected component.

2. Step 2: Differentiate BFS purpose from other graph properties

   While BFS can find shortest paths, here it is used to find connected nodes, not just paths or degrees.

3. Final Answer:

   All nodes reachable from a starting node forming one connected component -> Option A

4. Quick Check:

   BFS finds connected components = A [OK]

Hint: BFS visits all nodes in one component starting from any node [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges or degrees
• Assuming BFS finds all components at once

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

easy

A. let mut queue: VecDeque<usize> = VecDeque::new();

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

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

D. let queue: LinkedList<usize> = LinkedList::new();

Solution

1. Step 1: Identify correct queue type for BFS in Rust

   BFS requires a queue with efficient push/pop from front; VecDeque supports this.

2. Step 2: Check other options for correctness

   Vec is a stack-like structure, HashMap is a key-value store, LinkedList is less common and less efficient for BFS.

3. Final Answer:

   let mut queue: VecDeque<usize> = VecDeque::new(); -> Option A

4. Quick Check:

   Use VecDeque for BFS queue in Rust = C [OK]

Hint: Use VecDeque for queue to push/pop efficiently in BFS [OK]

Common Mistakes:

• Using Vec which is inefficient for queue operations
• Using HashMap instead of a queue
• Confusing LinkedList with VecDeque

3. Given the Rust code below for BFS connected components, what is the output?

use std::collections::{VecDeque, HashMap};

fn bfs(start: usize, graph: &HashMap, visited: &mut Vec<bool>) -> Vec<usize> {
    let mut queue = VecDeque::new();
    let mut component = Vec::new();
    queue.push_back(start);
    visited[start] = true;

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

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, vec![1]);
    graph.insert(1, vec![0, 2]);
    graph.insert(2, vec![1]);
    graph.insert(3, vec![4]);
    graph.insert(4, vec![3]);

    let mut visited = vec![false; 5];
    let comp1 = bfs(0, &graph, &mut visited);
    let comp2 = bfs(3, &graph, &mut visited);

    println!("Component 1: {:?}", comp1);
    println!("Component 2: {:?}", comp2);
}

medium

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

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

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

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

Solution

1. Step 1: Trace BFS from node 0

   Starting at 0, BFS visits 0, then 1, then 2. So component 1 is [0, 1, 2].

2. Step 2: Trace BFS from node 3

   Starting at 3, BFS visits 3, then 4. So component 2 is [3, 4].

3. Final Answer:

   Component 1: [0, 1, 2] Component 2: [3, 4] -> Option D

4. Quick Check:

   BFS groups connected nodes correctly = D [OK]

Hint: Follow BFS queue order to list connected nodes [OK]

Common Mistakes:

• Mixing nodes between components
• Ignoring visited array updates
• Assuming BFS order is sorted

4. Identify the bug in this BFS connected components Rust code snippet:

fn bfs(start: usize, graph: &HashMap, visited: &mut Vec<bool>) -> Vec<usize> {
    let mut queue = VecDeque::new();
    let mut component = Vec::new();
    queue.push_back(start);
    // visited[start] = true;  // Missing this line

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

medium

A. Neighbors are not checked for existence

B. The queue is not initialized properly

C. The starting node is not marked visited before BFS loop

D. Component vector is not returned

Solution

1. Step 1: Check visited marking for start node

   The line marking start node as visited is commented out, so BFS may revisit it causing infinite loop or wrong results.

2. Step 2: Verify other parts of code

   Queue is initialized, neighbors checked, and component returned correctly.

3. Final Answer:

   The starting node is not marked visited before BFS loop -> Option C

4. Quick Check:

   Mark start visited before BFS = A [OK]

Hint: Always mark start node visited before BFS loop [OK]

Common Mistakes:

• Forgetting to mark start visited
• Not initializing queue
• Ignoring neighbor existence check

5. You have a graph with 6 nodes (0 to 5) and edges: (0-1), (1-2), (3-4). Using BFS connected components, how many components are there and which nodes belong to each? Choose the correct grouping.

medium

A. 2 components: [0,1,2,3,4], [5]

B. 3 components: [0,1,2], [3,4], [5] (isolated node)

C. 1 component: [0,1,2,3,4,5]

D. 4 components: [0], [1,2], [3,4], [5]

Solution

1. Step 1: Identify connected groups from edges

   Edges connect 0-1-2 forming one component, 3-4 forming second, and node 5 is isolated alone.

2. Step 2: Count components and list nodes

   There are 3 components: [0,1,2], [3,4], and [5].

3. Final Answer:

   3 components: [0,1,2], [3,4], [5] (isolated node) -> Option B

4. Quick Check:

   Count isolated and connected groups correctly = B [OK]

Hint: Count isolated nodes as separate components [OK]

Common Mistakes:

• Grouping isolated node with others
• Merging disconnected components
• Miscounting total components