Connected Components Using BFS in DSA C# - Execution Trace

Concept Flow - Connected Components Using BFS

Start with graph

↓

Initialize visited set

↓

For each node in graph

↓

If node not visited?

No→Skip to next node

Yes↓

Start BFS from node

↓

Add node to queue and visited

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor

↓

If neighbor not visited

↓

Add neighbor to queue and visited

↓

Repeat until queue empty

↓

Mark one connected component found

↓

Repeat for all nodes

↓

Done: All connected components identified

We visit each node; if unvisited, we run BFS to find all nodes connected to it, marking one connected component. Repeat until all nodes are visited.

Execution Sample

DSA C#

var graph = new Dictionary<int, List<int>> {
  {0, new List<int>{1}},
  {1, new List<int>{0, 2}},
  {2, new List<int>{1}},
  {3, new List<int>{4}},
  {4, new List<int>{3}}
};
var visited = new HashSet<int>();
int components = 0;

void BFS(int start) {
  var queue = new Queue<int>();
  queue.Enqueue(start);
  visited.Add(start);

  while (queue.Count > 0) {
    int node = queue.Dequeue();
    foreach (var neighbor in graph[node]) {
      if (!visited.Contains(neighbor)) {
        visited.Add(neighbor);
        queue.Enqueue(neighbor);
      }
    }
  }
}

foreach (var node in graph.Keys) {
  if (!visited.Contains(node)) {
    BFS(node);
    components++;
  }
}

This code finds connected components in a graph using BFS, counting how many groups of connected nodes exist.

Execution Table

Step	Operation	Current Node	Queue	Visited Set	Connected Components Count	Visual State
1	Start	-	[]	{}	0	Graph: 0--1--2 and 3--4
2	Check node 0 visited?	-	[]	{}	0	Node 0 unvisited, start BFS
3	Add node 0 to queue and visited	0	[0]	{0}	0	Queue: [0], Visited: {0}
4	Dequeue node 0	0	[]	{0}	0	Processing node 0
5	Check neighbors of 0: [1]	0	[]	{0}	0	Neighbor 1 unvisited
6	Add neighbor 1 to queue and visited	1	[1]	{0,1}	0	Queue: [1], Visited: {0,1}
7	Dequeue node 1	1	[]	{0,1}	0	Processing node 1
8	Check neighbors of 1: [0,2]	1	[]	{0,1}	0	Neighbor 0 visited, neighbor 2 unvisited
9	Add neighbor 2 to queue and visited	2	[2]	{0,1,2}	0	Queue: [2], Visited: {0,1,2}
10	Dequeue node 2	2	[]	{0,1,2}	0	Processing node 2
11	Check neighbors of 2: [1]	2	[]	{0,1,2}	0	Neighbor 1 visited, no new nodes
12	Queue empty, BFS done for component	-	[]	{0,1,2}	1	Connected component 1 found: nodes 0,1,2
13	Check node 1 visited?	-	[]	{0,1,2}	1	Node 1 visited, skip
14	Check node 2 visited?	-	[]	{0,1,2}	1	Node 2 visited, skip
15	Check node 3 visited?	-	[]	{0,1,2}	1	Node 3 unvisited, start BFS
16	Add node 3 to queue and visited	3	[3]	{0,1,2,3}	1	Queue: [3], Visited: {0,1,2,3}
17	Dequeue node 3	3	[]	{0,1,2,3}	1	Processing node 3
18	Check neighbors of 3: [4]	3	[]	{0,1,2,3}	1	Neighbor 4 unvisited
19	Add neighbor 4 to queue and visited	4	[4]	{0,1,2,3,4}	1	Queue: [4], Visited: {0,1,2,3,4}
20	Dequeue node 4	4	[]	{0,1,2,3,4}	1	Processing node 4
21	Check neighbors of 4: [3]	4	[]	{0,1,2,3,4}	1	Neighbor 3 visited, no new nodes
22	Queue empty, BFS done for component	-	[]	{0,1,2,3,4}	2	Connected component 2 found: nodes 3,4
23	Check node 4 visited?	-	[]	{0,1,2,3,4}	2	Node 4 visited, skip
24	All nodes checked, done	-	[]	{0,1,2,3,4}	2	Total connected components: 2

💡 All nodes visited; BFS completed for all connected components.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 16	After Step 19	After Step 22	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2,3}	{0,1,2,3,4}	{0,1,2,3,4}	{0,1,2,3,4}
queue	[]	[0]	[1]	[2]	[]	[3]	[4]	[]	[]
components	0	0	0	0	1	1	1	2	2

Key Moments - 3 Insights

Why do we check if a node is visited before starting BFS?

Because if a node is already visited, it means it belongs to a connected component we already found. Starting BFS again would repeat work. See execution_table rows 2, 13, 14, 15.

Why do we add neighbors to the queue only if they are not visited?

Adding only unvisited neighbors prevents revisiting nodes and infinite loops. This is shown in rows 5, 8, 11, 18, 21 where visited neighbors are skipped.

How do we know when one connected component is fully found?

When the BFS queue becomes empty, it means all reachable nodes from the start node are visited. This is shown in rows 12 and 22 where BFS ends and component count increases.

Visual Quiz - 3 Questions

Look at the execution_table at step 9. What nodes are in the visited set?

A {0,1,2}

B {0,1}

C {0,1,2,3}

D {1,2}

💡 Hint

Check the 'Visited Set' column at step 9 in the execution_table.

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

A Step 10

B Step 12

C Step 15

D Step 22

💡 Hint

Look for the row where the queue becomes empty and components count increases to 1.

If node 3 was already visited before step 15, how many connected components would be found?

A 3

B 2

C 1

D 0

💡 Hint

Refer to the 'components' variable in variable_tracker and consider skipping BFS from node 3.

Concept Snapshot

Connected Components Using BFS:
- Visit each node in graph
- If unvisited, start BFS
- BFS visits all nodes connected to start node
- Mark visited nodes to avoid repeats
- Each BFS run finds one connected component
- Count components by number of BFS runs

Full Transcript

Connected Components Using BFS means we find groups of nodes connected together in a graph. We start with an empty set of visited nodes. For each node, if it is not visited, we run BFS starting from it. BFS uses a queue to visit nodes layer by layer. We add neighbors to the queue only if they are not visited. When BFS finishes (queue empty), we have found one connected component. We repeat for all nodes. The total number of BFS runs equals the number of connected components. This method ensures we visit every node exactly once and count all connected groups in the graph.

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