Connected Components Using BFS in DSA Go - 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

↓

Mark node visited, add to queue

↓

While queue not empty

↓

Pop node from queue

↓

For each neighbor

↓

If neighbor not visited

↓

Mark visited, add to queue

↓

Continue until queue empty

↓

One connected component found

↓

Repeat for next unvisited node

↓

All nodes visited, done

We check each node; if unvisited, we run BFS to find all nodes connected to it, marking them visited. Each BFS run finds one connected component.

Execution Sample

DSA Go

graph := map[int][]int{
  1: {2},
  2: {1, 3},
  3: {2},
  4: {5},
  5: {4},
}
visited := map[int]bool{}
var bfs func(int)
bfs = func(start int) {
  queue := []int{start}
  visited[start] = true
  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    for _, neighbor := range graph[node] {
      if !visited[neighbor] {
        visited[neighbor] = true
        queue = append(queue, neighbor)
      }
    }
  }
}
for node := range graph {
  if !visited[node] {
    bfs(node)
  }
}

This code finds connected components in a graph using BFS, marking nodes visited as it explores.

Execution Table

Step	Operation	Current Node	Visited Set	Queue	Connected Component	Visual State
1	Start BFS from node 1	1	{}	[1]	[ ]	1: [] 2: [] 3: [] 4: [] 5: []
2	Pop from queue	1	{1}	[]	[1]	1: visited 2: [] 3: [] 4: [] 5: []
3	Check neighbors of 1	1	{1}	[]	[1]	Neighbors: 2
4	Visit neighbor 2	2	{1,2}	[2]	[1,2]	2 marked visited, added to queue
5	Pop from queue	2	{1,2}	[]	[1,2]	2 visited
6	Check neighbors of 2	2	{1,2}	[]	[1,2]	Neighbors: 1,3
7	Neighbor 1 already visited	2	{1,2}	[]	[1,2]	Skip 1
8	Visit neighbor 3	3	{1,2,3}	[3]	[1,2,3]	3 marked visited, added to queue
9	Pop from queue	3	{1,2,3}	[]	[1,2,3]	3 visited
10	Check neighbors of 3	3	{1,2,3}	[]	[1,2,3]	Neighbor: 2
11	Neighbor 2 already visited	3	{1,2,3}	[]	[1,2,3]	Skip 2
12	Queue empty, component complete	-	{1,2,3}	[]	[1,2,3]	Component found: 1,2,3
13	Next node 2 visited, skip	2	{1,2,3}	[]	[1,2,3]	Skip 2
14	Next node 3 visited, skip	3	{1,2,3}	[]	[1,2,3]	Skip 3
15	Next node 4 unvisited, start BFS	4	{1,2,3}	[4]	[1,2,3]	Start BFS for component 2
16	Pop from queue	4	{1,2,3,4}	[]	[1,2,3,4]	4 visited
17	Check neighbors of 4	4	{1,2,3,4}	[]	[1,2,3,4]	Neighbor: 5
18	Visit neighbor 5	5	{1,2,3,4,5}	[5]	[1,2,3,4,5]	5 marked visited, added to queue
19	Pop from queue	5	{1,2,3,4,5}	[]	[1,2,3,4,5]	5 visited
20	Check neighbors of 5	5	{1,2,3,4,5}	[]	[1,2,3,4,5]	Neighbor: 4
21	Neighbor 4 already visited	5	{1,2,3,4,5}	[]	[1,2,3,4,5]	Skip 4
22	Queue empty, component complete	-	{1,2,3,4,5}	[]	[1,2,3,4,5]	Component found: 4,5
23	Next node 5 visited, skip	5	{1,2,3,4,5}	[]	[1,2,3,4,5]	Skip 5
24	All nodes visited, done	-	{1,2,3,4,5}	[]	[1,2,3,4,5]	All components found

💡 All nodes visited, BFS completed for each connected component

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 12	After Step 18	After Step 22	Final
visited	{}	{1,2}	{1,2,3}	{1,2,3}	{1,2,3,4,5}	{1,2,3,4,5}	{1,2,3,4,5}
queue	[]	[2]	[3]	[]	[5]	[]	[]
connected_component	[]	[1,2]	[1,2,3]	[1,2,3]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]

Key Moments - 3 Insights

Why do we skip nodes that are already visited in the main loop?

Because those nodes are already part of a connected component found by a previous BFS, skipping avoids repeated work. See steps 13 and 14 where nodes 2 and 3 are skipped.

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

Adding only unvisited neighbors prevents infinite loops and repeated visits. This is shown in steps 7 and 11 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. See steps 12 and 22 where queue empties mark component completion.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after step 8?

A {1,2,3}

B {1,2}

C {1}

D {}

💡 Hint

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

At which step does the BFS queue become empty for the first connected component?

A Step 9

B Step 12

C Step 6

D Step 4

💡 Hint

Look for the step where 'Queue' is empty and component is marked complete in the execution_table.

If node 4 was connected to node 3, how would the connected components change?

A There would be one connected component containing all nodes 1 to 5

B There would still be two connected components

C Node 4 would be isolated

D Node 5 would be isolated

💡 Hint

Consider how BFS explores neighbors and merges connected nodes into one component.

Concept Snapshot

Connected Components Using BFS:
- For each unvisited node, run BFS
- Mark nodes visited as you explore
- BFS queue holds nodes to visit
- When queue empties, one component found
- Repeat until all nodes visited

Full Transcript

This visualization shows how BFS finds connected components in a graph. We start with an empty visited set and check each node. If a node is unvisited, we run BFS from it, marking nodes visited and adding neighbors to a queue. We pop nodes from the queue, visit their neighbors, and continue until the queue is empty. This marks one connected component. We then continue with the next unvisited node until all nodes are visited. The execution table tracks each step, showing the current node, visited set, queue contents, and connected components found. Key moments clarify why we skip visited nodes and how we know when a component is complete. The quiz tests understanding of visited sets, queue emptiness, and how connections affect components.

Practice

1. What does the BFS algorithm help find in an undirected graph when used for connected components?

easy

A. The total number of edges in the graph

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

D. All nodes reachable from a starting node forming one connected component

Solution

1. Step 1: Understand BFS role in connected components

   BFS explores all nodes reachable from a given start node, grouping them as one connected component.

2. Step 2: Differentiate BFS from other graph properties

   BFS does not directly find shortest paths between arbitrary nodes, max degree, or edge count in this context.

3. Final Answer:

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

4. Quick Check:

   BFS finds connected components [OK]

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

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges or degrees
• Mixing connected components with graph size

2. Which of the following Go code snippets correctly initializes a queue for BFS traversal?

easy

A. queue := []int{} // empty slice for BFS queue

B. queue := make(map[int]bool) // map used as queue

C. queue := 0 // integer used as queue

D. queue := "queue" // string used as queue"

Solution

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

   BFS requires a queue to hold nodes; a slice of ints is a common and correct choice in Go.

2. Step 2: Eliminate incorrect queue initializations

   Maps, integers, or strings cannot function as queues for BFS traversal.

3. Final Answer:

   queue := []int{} // empty slice for BFS queue -> Option A

4. Quick Check:

   Queue for BFS = slice of ints [OK]

Hint: Use slice of ints as queue in Go BFS [OK]

Common Mistakes:

• Using map instead of slice for queue
• Using integer or string as queue
• Not initializing queue before BFS

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

graph := map[int][]int{
  0: {1},
  1: {0, 2},
  2: {1},
  3: {4},
  4: {3},
  5: {},
}

visited := make(map[int]bool)
count := 0
for node := range graph {
  if !visited[node] {
    queue := []int{node}
    visited[node] = true
    for len(queue) > 0 {
      current := queue[0]
      queue = queue[1:]
      for _, neighbor := range graph[current] {
        if !visited[neighbor] {
          visited[neighbor] = true
          queue = append(queue, neighbor)
        }
      }
    }
    count++
  }
}
fmt.Println(count)

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Identify connected components in the graph

   Nodes 0,1,2 form one component; nodes 3,4 form second; node 5 alone forms third.

2. Step 2: BFS visits each component once, incrementing count

   Loop visits nodes 0,3,5 as unvisited starts, counting 3 components total.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 connected components = 3 [OK]

Hint: Count BFS starts on unvisited nodes [OK]

Common Mistakes:

• Counting edges instead of components
• Missing isolated nodes as components
• Not marking visited nodes properly

4. The following BFS code for counting connected components has a bug. What is the error?

func countComponents(graph map[int][]int) int {
  visited := make(map[int]bool)
  count := 0
  for node := range graph {
    if visited[node] {
      queue := []int{node}
      visited[node] = true
      for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[current] {
          if !visited[neighbor] {
            visited[neighbor] = true
            queue = append(queue, neighbor)
          }
        }
      }
      count++
    }
  }
  return count
}

medium

A. The visited map is not initialized

B. The queue initialization is incorrect

C. The condition should be if !visited[node], not if visited[node]

D. The count variable is not incremented

Solution

1. Step 1: Analyze the if condition for BFS start

   The code starts BFS only if visited[node] is true, which is wrong; it should start if node is not visited.

2. Step 2: Understand impact on BFS traversal

   Because of wrong condition, BFS never starts, so count remains zero incorrectly.

3. Final Answer:

   The condition should be if !visited[node], not if visited[node] -> Option C

4. Quick Check:

   Start BFS on unvisited nodes [OK]

Hint: Start BFS only if node is unvisited [OK]

Common Mistakes:

• Using visited[node] instead of !visited[node]
• Not initializing visited map
• Forgetting to increment count

5. You have a graph with nodes 0 to 6 and edges: (0-1), (1-2), (3-4), (5-6). Using BFS to find connected components, what is the count if node 7 is isolated and missing from the adjacency list? Choose the correct approach to count all components including isolated nodes.

hard

A. Count only nodes connected by edges

B. Include node 7 in the graph map with empty adjacency list before BFS

C. Ignore node 7 since it is not in adjacency list

D. Add node 7 as connected to node 0

Solution

1. Step 1: Recognize isolated nodes must be in graph map

   To count isolated nodes as components, they must appear in the graph with empty adjacency lists.

2. Step 2: Include node 7 with empty neighbors before BFS

   Adding node 7 ensures BFS visits it as a separate component.

3. Final Answer:

   Include node 7 in the graph map with empty adjacency list before BFS -> Option B

4. Quick Check:

   Isolated nodes need empty adjacency list [OK]

Hint: Add isolated nodes with empty lists to graph before BFS [OK]

Common Mistakes:

• Ignoring isolated nodes not in adjacency list
• Assuming isolated nodes are counted automatically
• Connecting isolated nodes incorrectly