Connected Components Using BFS in DSA C#

Mental Model

We find groups of nodes where each node can reach every other node in the same group by walking through edges step-by-step.

Analogy: Imagine a group of friends at a party where everyone in a group can talk to each other by passing messages through mutual friends. Each group is a connected component.

Graph:
0 -> 1 -> 2
3 -> 4
5

Here, nodes 0,1,2 form one group; 3,4 another; and 5 alone.

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 3-4; nodes: 0 to 5

Goal: Identify all connected groups of nodes using BFS

Step 1: Start BFS from node 0, mark it visited and add to component

Visited: {0}
Queue: [0]
Components: []

Why: We begin exploring from the first unvisited node to find its group

Step 2: Dequeue 0, enqueue its neighbor 1, mark visited

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

Why: Explore neighbors to find all connected nodes

Step 3: Dequeue 1, enqueue neighbor 2, mark visited

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

Why: Continue exploring connected nodes

Step 4: Dequeue 2, no new neighbors to visit

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

Why: Finished exploring this connected group

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

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

Why: Find next connected group

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

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

Why: Explore neighbors in this group

Step 7: Dequeue 4, no new neighbors

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

Why: Finished exploring second group

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

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

Why: Last node alone forms its own group

Step 9: Dequeue 5, no neighbors

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

Why: Finished exploring last group

Result:

Groups found:
Group 1: 0 -> 1 -> 2 -> null
Group 2: 3 -> 4 -> null
Group 3: 5 -> null

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private readonly int V;
    private readonly List<int>[] adj;

    public Graph(int vertices) {
        V = vertices;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    public List<List<int>> ConnectedComponents() {
        bool[] visited = new bool[V];
        List<List<int>> components = new List<List<int>>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                List<int> component = new List<int>();
                BFS(i, visited, component);
                components.Add(component);
            }
        }
        return components;
    }

    private void BFS(int start, bool[] visited, List<int> component) {
        Queue<int> queue = new Queue<int>();
        visited[start] = true; // mark start visited
        queue.Enqueue(start); // enqueue start node

        while (queue.Count > 0) {
            int node = queue.Dequeue(); // dequeue current node
            component.Add(node); // add to current component

            foreach (int neighbor in adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // mark neighbor visited
                    queue.Enqueue(neighbor); // enqueue neighbor
                }
            }
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(6);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(3, 4);

        List<List<int>> components = g.ConnectedComponents();

        int count = 1;
        foreach (var comp in components) {
            Console.Write($"Group {count}: ");
            for (int i = 0; i < comp.Count; i++) {
                Console.Write(comp[i]);
                if (i != comp.Count - 1) Console.Write(" -> ");
            }
            Console.WriteLine(" -> null");
            count++;
        }
    }
}

if (!visited[i]) {

start BFS from each unvisited node to find a new connected component

visited[start] = true; // mark start visited

mark the starting node as visited to avoid revisiting

queue.Enqueue(start); // enqueue start node

add starting node to queue to begin BFS traversal

int node = queue.Dequeue(); // dequeue current node

process nodes in BFS order by dequeuing from queue

component.Add(node); // add to current component

add the current node to the connected component list

if (!visited[neighbor]) {

check if neighbor is unvisited before adding to queue

visited[neighbor] = true; // mark neighbor visited

mark neighbor visited to prevent repeated processing

queue.Enqueue(neighbor); // enqueue neighbor

enqueue neighbor to continue BFS traversal

Output

Group 1: 0 -> 1 -> 2 -> null

Group 2: 3 -> 4 -> null

Group 3: 5 -> null

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for the visited array, queue, and storing components

vs Alternative: Compared to DFS, BFS has similar time and space but uses a queue instead of recursion stack

Edge Cases

Graph with no edges (all nodes isolated)

Each node forms its own connected component

DSA C#

if (!visited[i]) {

Graph with a single node

Returns one component with that single node

DSA C#

if (!visited[i]) {

Graph with all nodes connected

Returns one component containing all nodes

DSA C#

if (!visited[i]) {

When to Use This Pattern

When you need to find isolated groups or clusters in a graph, use BFS to explore each group fully before moving to the next.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes as visited immediately when enqueueing to avoid revisiting

Mistake: Starting BFS from every node without checking visited leads to duplicate components
Fix: Only start BFS from unvisited nodes to find new components

Summary

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

Use when you want to identify isolated clusters or connected parts in a network.

The key is to explore all reachable nodes from a start node before moving to the next unvisited node.

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

C. The node with the highest degree

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 given start node, marking them as part of the same connected component.

2. Step 2: Identify what BFS finds in this use case

   It finds all nodes connected directly or indirectly to the start node, grouping them as one connected component.

3. Final Answer:

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

4. Quick Check:

   BFS finds connected nodes = D [OK]

Hint: BFS visits all nodes in one connected group [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges instead of nodes
• Assuming BFS finds node degrees

2. Which of the following is the correct way to declare a queue for BFS in C#?

easy

A. Dictionary queue = new Dictionary();

B. List<int> queue = new List<int>();

C. Stack<int> queue = new Stack<int>();

D. Queue<int> queue = new Queue<int>();

Solution

1. Step 1: Identify the data structure for BFS queue

   BFS requires a queue to process nodes in FIFO order, so Queue<T> is used in C#.

2. Step 2: Check syntax correctness

   Queue<int> queue = new Queue<int>(); correctly declares an empty queue of integers.

3. Final Answer:

   Queue<int> queue = new Queue<int>(); -> Option D

4. Quick Check:

   Queue declaration for BFS = A [OK]

Hint: Use Queue<T> for BFS traversal in C# [OK]

Common Mistakes:

• Using List instead of Queue for BFS
• Using Stack which is LIFO, not FIFO
• Confusing Dictionary with queue

3. Given the following graph adjacency list and BFS code snippet, what is the output list of connected components?

var graph = new Dictionary {
  {1, new List<int>{2}},
  {2, new List<int>{1, 3}},
  {3, new List<int>{2}},
  {4, new List<int>{5}},
  {5, new List<int>{4}}
};

List connectedComponents = new List();
HashSet<int> visited = new HashSet<int>();

foreach (var node in graph.Keys) {
  if (!visited.Contains(node)) {
    Queue<int> queue = new Queue<int>();
    List<int> component = new List<int>();
    queue.Enqueue(node);
    visited.Add(node);
    while (queue.Count > 0) {
      int current = queue.Dequeue();
      component.Add(current);
      foreach (var neighbor in graph[current]) {
        if (!visited.Contains(neighbor)) {
          visited.Add(neighbor);
          queue.Enqueue(neighbor);
        }
      }
    }
    connectedComponents.Add(component);
  }
}

foreach (var comp in connectedComponents) {
  Console.WriteLine(string.Join(",", comp));
}

medium

A. "1,2,3\n4,5"

B. "1,3,2\n4,5"

C. "1,2\n3,4,5"

D. "1,2,3,4,5"

Solution

1. Step 1: Trace BFS from node 1

   Starting at 1, BFS visits 1, then 2, then 3. Component is [1,2,3].

2. Step 2: Trace BFS from node 4

   Next unvisited node is 4, BFS visits 4 and 5. Component is [4,5].

3. Final Answer:

   "1,2,3\n4,5" -> Option A

4. Quick Check:

   Connected components = [1,2,3] and [4,5] [OK]

Hint: BFS groups connected nodes in order visited [OK]

Common Mistakes:

• Mixing order of nodes in components
• Assuming all nodes are in one component
• Forgetting to mark visited nodes

4. Identify the bug in the following BFS code for connected components:

foreach (var node in graph.Keys) {
  if (!visited.Contains(node)) {
    Queue<int> queue = new Queue<int>();
    List<int> component = new List<int>();
    queue.Enqueue(node);
    // Missing visited.Add(node);
    while (queue.Count > 0) {
      int current = queue.Dequeue();
      component.Add(current);
      foreach (var neighbor in graph[current]) {
        if (!visited.Contains(neighbor)) {
          visited.Add(neighbor);
          queue.Enqueue(neighbor);
        }
      }
    }
    connectedComponents.Add(component);
  }
}

medium

A. Neighbors are not added to the queue

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

C. The queue is not initialized

D. The component list is not cleared

Solution

1. Step 1: Check visited marking for start node

   The code does not mark the starting node as visited before BFS, so it may be processed multiple times.

2. Step 2: Understand BFS consequences

   Without marking start node visited, BFS can enqueue it repeatedly causing infinite loop or wrong components.

3. Final Answer:

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

4. Quick Check:

   Start node must be visited first [OK]

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

Common Mistakes:

• Forgetting to mark start node visited
• Marking visited after enqueueing neighbors only
• Not initializing queue properly

5. You have a graph with nodes 1 to 7 and edges: (1-2), (2-3), (4-5), (5-6), (6-4), (7). Using BFS to find connected components, how many components will be found and which nodes belong to the largest component?

hard

A. 3 components; largest component nodes: [4,5,6,7]

B. 2 components; largest component nodes: [1,2,3,4,5,6]

C. 3 components; largest component nodes: [4,5,6]

D. 4 components; largest component nodes: [1,2,3]

Solution

1. Step 1: Identify connected components from edges

   Edges form three groups: (1,2,3), (4,5,6), and isolated node (7). So 3 components total.

2. Step 2: Determine largest component

   Components (1,2,3) and (4,5,6) both have 3 nodes; largest size is 3. 3 components; largest component nodes: [4,5,6] correctly lists [4,5,6].

3. Final Answer:

   3 components; largest component nodes: [4,5,6] -> Option C

4. Quick Check:

   3 components, largest = [4,5,6] [OK]

Hint: Count isolated groups; largest has most nodes [OK]

Common Mistakes:

• Counting isolated node as connected
• Merging separate components incorrectly
• Miscounting number of components