Connected Components Using BFS in DSA Rust - Execution Trace

Concept Flow - Connected Components Using BFS

Start with all nodes unvisited

↓

Pick an unvisited node

↓

Initialize BFS queue with this node

↓

While queue not empty

↓

Dequeue node

↓

Mark node visited, add to current component

↓

Enqueue all unvisited neighbors

↓

Repeat until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited -> Done

We find connected components by repeatedly running BFS from unvisited nodes, marking all reachable nodes as one component.

Execution Sample

DSA Rust

fn bfs_component(graph: &Vec<Vec<usize>>, start: usize, visited: &mut Vec<bool>) -> Vec<usize> {
    let mut queue = Vec::new();
    let mut component = Vec::new();
    queue.push(start);
    visited[start] = true;
    while let Some(node) = queue.pop() {
        component.push(node);
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.insert(0, neighbor);
            }
        }
    }
    component
}

This BFS function finds all nodes connected to 'start' and returns them as one connected component.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Component Nodes	Visual State
1	Start BFS from node 0	-	[0]	{}	[]	Graph nodes: 0,1,2,3,4,5; All unvisited
2	Dequeue node	0	[]	{0}	[0]	Visited 0; Queue empty
3	Enqueue neighbors of 0	-	[1,2]	{0}	[0]	Neighbors 1,2 added to queue
4	Dequeue node	2	[1]	{0,2}	[0,2]	Visited 2; Queue has 1
5	Enqueue neighbors of 2	-	[1,3]	{0,2}	[0,2]	Neighbor 3 added
6	Dequeue node	3	[1]	{0,2,3}	[0,2,3]	Visited 3; Queue has 1
7	Enqueue neighbors of 3	-	[1]	{0,2,3}	[0,2,3]	No new neighbors
8	Dequeue node	1	[]	{0,1,2,3}	[0,2,3,1]	Visited 1; Queue empty
9	Enqueue neighbors of 1	-	[]	{0,1,2,3}	[0,2,3,1]	No new neighbors
10	Queue empty, component complete	-	[]	{0,1,2,3}	[0,2,3,1]	Component found: {0,1,2,3}
11	Start BFS from next unvisited node 4	-	[4]	{0,1,2,3}	[]	Start new component
12	Dequeue node	4	[]	{0,1,2,3,4}	[4]	Visited 4; Queue empty
13	Enqueue neighbors of 4	-	[5]	{0,1,2,3,4}	[4]	Neighbor 5 added
14	Dequeue node	5	[]	{0,1,2,3,4,5}	[4,5]	Visited 5; Queue empty
15	Enqueue neighbors of 5	-	[]	{0,1,2,3,4,5}	[4,5]	No new neighbors
16	Queue empty, component complete	-	[]	{0,1,2,3,4,5}	[4,5]	Component found: {4,5}
17	All nodes visited, done	-	[]	{0,1,2,3,4,5}	[4,5]	All components found

💡 All nodes visited, BFS completed for all connected components

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	After Step 16	Final
visited	{ }	{0}	{0,2}	{0,2,3}	{0,1,2,3}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4,5}	{0,1,2,3,4,5}	{0,1,2,3,4,5}
queue	[]	[]	[1]	[1]	[]	[]	[4]	[]	[]	[]
component	[]	[0]	[0,2]	[0,2,3]	[0,2,3,1]	[0,2,3,1]	[]	[4]	[4,5]	[4,5]

Key Moments - 3 Insights

Why do we mark a node visited immediately when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see steps 3,5,7) prevents adding the same node multiple times to the queue, avoiding repeated visits and infinite loops.

Why does BFS stop when the queue is empty?

When the queue is empty (steps 10,16), it means all reachable nodes from the start node are visited, so the current connected component is fully found.

How do we find all connected components in the graph?

After finishing BFS from one node (step 10), we pick the next unvisited node (step 11) and run BFS again, repeating until all nodes are visited (step 17).

Visual Quiz - 3 Questions

Look at the execution table at step 4, which node is dequeued and visited?

A Node 1

B Node 3

C Node 2

D Node 0

💡 Hint

Check the 'Current Node' column at step 4 in the execution_table

At which step does the BFS finish exploring the first connected component?

A Step 10

B Step 8

C Step 12

D Step 16

💡 Hint

Look for the step where the queue becomes empty and the first component is complete in the execution_table

If node 3 had an additional neighbor 5, how would the queue state change at step 7?

A Queue would include node 4

B Queue would include node 5 after step 7

C Queue would be empty as before

D Queue would include nodes 4 and 5

💡 Hint

Check how neighbors are enqueued in the execution_table at step 7

Concept Snapshot

Connected Components Using BFS:
- Start BFS from any unvisited node
- Use a queue to explore neighbors
- Mark nodes visited when enqueued
- Collect nodes visited in one BFS as one component
- Repeat BFS for all unvisited nodes
- Stops when all nodes are visited

Full Transcript

This visualization shows how BFS finds connected components in a graph. We start with all nodes unvisited. We pick an unvisited node and run BFS, using a queue to explore all reachable nodes. Each visited node is marked to avoid repeats. When the queue empties, one connected component is found. We then pick the next unvisited node and repeat until all nodes are visited. The execution table tracks each step: which node is dequeued, queue contents, visited nodes, and the current component. Key moments clarify why nodes are marked visited when enqueued, why BFS stops when the queue is empty, and how multiple BFS runs find all components. The quiz tests understanding of node visits, BFS completion, and queue changes with graph modifications.

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