Connected Components Using BFS in DSA C# - Build from Scratch

Connected Components Using BFS

📖 Scenario: You are working with a simple map of cities connected by roads. Each city is a node, and roads are connections between them. Some cities are connected directly or through other cities, forming groups called connected components.We want to find how many groups of connected cities exist using a method called Breadth-First Search (BFS).

🎯 Goal: Build a program that finds the number of connected components in a graph using BFS. You will create the graph, set up a visited tracker, write BFS to explore connected cities, and count how many groups exist.

📋 What You'll Learn

Create a graph using a dictionary with exact city connections

Create a visited dictionary to track visited cities

Write a BFS function using a queue to explore connected cities

Count and print the number of connected components

💡 Why This Matters

🌍 Real World

Finding connected components helps in network analysis, like identifying isolated groups in social networks or clusters in maps.

💼 Career

Understanding BFS and connected components is essential for roles in software development, data analysis, and network engineering.

1

Create the graph data structure

Create a dictionary called graph with these exact entries: "A" connected to ["B", "C"], "B" connected to ["A", "D"], "C" connected to ["A"], "D" connected to ["B"], and "E" connected to [].

DSA C#

# Your code here

Hint

Use Dictionary<string, List<string>> to create the graph. Each city key maps to a list of connected cities.

2

Create the visited dictionary

Create a dictionary called visited with the same keys as graph and set all values to false.

DSA C#

using System.Collections.Generic;

var graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D" } },
    { "C", new List { "A" } },
    { "D", new List { "B" } },
    { "E", new List() }
};

// Your code here

Hint

Use a dictionary with city names as keys and false as initial values to mark them unvisited.

3

Write the BFS function

Write a function called BFS that takes a string start parameter. Use a Queue<string> to explore connected cities. Mark each visited city in visited as true. Use graph[start] to get neighbors.

DSA C#

using System.Collections.Generic;

var graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D" } },
    { "C", new List { "A" } },
    { "D", new List { "B" } },
    { "E", new List() }
};

var visited = new Dictionary
{
    { "A", false },
    { "B", false },
    { "C", false },
    { "D", false },
    { "E", false }
};

// Your code here

Hint

Use a queue to keep track of cities to visit. Mark each city visited when you add it to the queue.

4

Count and print connected components

Create an integer variable count set to 0. Use a foreach loop with city over graph.Keys. If visited[city] is false, call BFS(city) and increment count by 1. Finally, print count.

DSA C#

using System.Collections.Generic;

var graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D" } },
    { "C", new List { "A" } },
    { "D", new List { "B" } },
    { "E", new List() }
};

var visited = new Dictionary
{
    { "A", false },
    { "B", false },
    { "C", false },
    { "D", false },
    { "E", false }
};

void BFS(string start)
{
    var queue = new Queue();
    queue.Enqueue(start);
    visited[start] = true;

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

// Your code here

Hint

Each BFS call finds one connected group. Count how many times BFS is called for unvisited cities.

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