Connected Components Using BFS in DSA Rust

Mental Model

We find groups of nodes where each node can reach any other node in the same group by walking through edges. BFS helps explore each group fully before moving to the next.

Analogy: Imagine a party where people hold hands forming groups. BFS is like starting from one person and visiting everyone connected by holding hands until the whole group is found, then moving to another group.

Graph:
0 -> 1
|
2

Groups:
[0,1,2]  [3,4]

Adjacency list:
0 -> [1,2]
1 -> [0]
2 -> [0]
3 -> [4]
4 -> [3]

Dry Run Walkthrough

Input: Graph with edges: 0-1, 0-2, 3-4; find connected components

Goal: Identify all connected groups of nodes using BFS

Step 1: Start BFS from node 0, mark 0 visited

Visited: {0}
Queue: [0]

Why: We begin exploring the first group from node 0

Step 2: Dequeue 0, enqueue neighbors 1 and 2, mark visited

Visited: {0,1,2}
Queue: [1,2]

Why: Explore all nodes connected to 0

Step 3: Dequeue 1, neighbors are 0 (visited), skip

Visited: {0,1,2}
Queue: [2]

Why: No new nodes to add from 1

Step 4: Dequeue 2, neighbors are 0 (visited), skip

Visited: {0,1,2}
Queue: []

Why: Finished exploring first group

Step 5: Move to next unvisited node 3, start BFS, mark 3 visited

Visited: {0,1,2,3}
Queue: [3]

Why: Start exploring second group

Step 6: Dequeue 3, enqueue neighbor 4, mark visited

Visited: {0,1,2,3,4}
Queue: [4]

Why: Add connected node 4 to group

Step 7: Dequeue 4, neighbors 3 visited, skip

Visited: {0,1,2,3,4}
Queue: []

Why: Finished exploring second group

Result:

Connected components:
Component 1: 0 -> 1 -> 2
Component 2: 3 -> 4

Annotated Code

DSA Rust

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

fn bfs_connected_components(graph: &Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let mut visited = HashSet::new();
    let mut components = Vec::new();

    for node in 0..graph.len() {
        if !visited.contains(&node) {
            let mut queue = VecDeque::new();
            let mut component = Vec::new();
            queue.push_back(node);
            visited.insert(node);

            while let Some(current) = queue.pop_front() {
                component.push(current);
                for &neighbor in &graph[current] {
                    if !visited.contains(&neighbor) {
                        queue.push_back(neighbor);
                        visited.insert(neighbor);
                    }
                }
            }
            components.push(component);
        }
    }
    components
}

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

    let components = bfs_connected_components(&graph);
    for (i, comp) in components.iter().enumerate() {
        print!("Component {}: ", i + 1);
        for &node in comp {
            print!("{} -> ", node);
        }
        println!("null");
    }
}

for node in 0..graph.len() {

iterate over all nodes to find unvisited starting points

if !visited.contains(&node) {

start BFS only from nodes not yet visited

queue.push_back(node); visited.insert(node);

initialize BFS queue and mark start node visited

while let Some(current) = queue.pop_front() {

process nodes in BFS order

component.push(current);

add current node to current connected component

for &neighbor in &graph[current] {

check all neighbors of current node

if !visited.contains(&neighbor) {

enqueue and mark neighbors not visited yet

components.push(component);

save the completed connected component

Output

Component 1: 0 -> 1 -> 2 -> null

Component 2: 3 -> 4 -> null

Complexity Analysis

Time: O(V + E) because each node and edge is visited once during BFS

Space: O(V) for the visited set, queue, and components storage

vs Alternative: Compared to DFS, BFS has similar time and space complexity but explores neighbors level by level

Edge Cases

Empty graph (no nodes)

Returns empty list of components

DSA Rust

for node in 0..graph.len() {

Graph with isolated nodes (no edges)

Each node forms its own component

DSA Rust

if !visited.contains(&node) {

Graph with one big connected component

Returns one component containing all nodes

DSA Rust

while let Some(current) = queue.pop_front() {

When to Use This Pattern

When asked to find groups of connected nodes in an undirected graph, use BFS to explore each group fully before moving to the next.

Common Mistakes

Mistake: Not marking nodes as visited when enqueued, causing infinite loops
Fix: Mark nodes as visited immediately when adding to the queue

Mistake: Starting BFS from every node without checking visited, causing repeated work
Fix: Check if node is visited before starting BFS

Summary

Finds all connected groups of nodes in a graph using breadth-first search.

Use when you need to identify separate connected parts in an undirected graph.

The key is to explore all neighbors of a node before moving to the next, ensuring full group discovery.

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