Connected Components Using BFS in DSA Rust - Build from Scratch

Connected Components Using BFS

📖 Scenario: You are working with a simple network of computers represented as an undirected graph. Each computer is a node, and connections between them are edges. You want to find groups of computers that are connected to each other directly or indirectly. These groups are called connected components.

🎯 Goal: Build a Rust program that finds all connected components in the network using Breadth-First Search (BFS). You will create the graph, set up a visited tracker, implement BFS to explore each component, and finally print the connected components.

📋 What You'll Learn

Create an undirected graph using a HashMap where keys are node IDs (usize) and values are vectors of connected nodes.

Create a HashSet to track visited nodes.

Implement BFS using a queue to explore nodes in each connected component.

Print each connected component as a vector of node IDs.

💡 Why This Matters

🌍 Real World

Finding connected components helps identify isolated groups in networks, social media clusters, or computer networks.

💼 Career

Understanding graph traversal and connected components is important for roles in software engineering, data analysis, and network security.

1

Create the graph data structure

Create a variable called graph as a HashMap<usize, Vec<usize>> with these exact entries: 1: vec![2], 2: vec![1, 3], 3: vec![2], 4: vec![5], 5: vec![4], 6: vec![].

DSA Rust

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

// Create the graph variable with given nodes and edges
// Your code here

Hint

Use HashMap::new() to create the graph. Use insert to add each node and its neighbors.

2

Create the visited set

Create a mutable HashSet<usize> called visited to keep track of visited nodes.

DSA Rust

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

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

    // Create visited set
    // Your code here
}

Hint

Use HashSet::new() to create an empty set for visited nodes.

3

Implement BFS to find connected components

Write a for loop over graph.keys() with variable node. Inside, check if node is not in visited. If not, create a VecDeque<usize> called queue, push node into it, and create a Vec<usize> called component. Use a while loop to pop from queue, mark nodes visited, add neighbors to queue if not visited, and add nodes to component. After the while loop, print the component vector.

DSA Rust

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

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

    let mut visited: HashSet = HashSet::new();

    // Implement BFS to find connected components
    // Your code here
}

Hint

Use a queue to explore neighbors level by level. Mark nodes visited when you pop them. Add neighbors to the queue only if not visited. Collect nodes in component vector.

4

Print the connected components

Run the program to print each connected component as a vector of node IDs. The output should show all groups of connected nodes.

DSA Rust

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

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

    let mut visited: HashSet = HashSet::new();

    for node in graph.keys() {
        if !visited.contains(node) {
            let mut queue: VecDeque = VecDeque::new();
            queue.push_back(*node);
            let mut component: Vec = Vec::new();

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

            // Print the component
            // Your code here
        }
    }
}

Hint

Run the program. It prints each connected component as a vector of node IDs. The output shows groups of connected computers.

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