Connected Components Using BFS in DSA Go

Mental Model

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

Analogy: Imagine a group of friends at a party where everyone in a group can talk to each other directly or through others. BFS helps us find each friend group by visiting one friend, then their friends, and so on until the whole group is found.

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

Groups:
[0,1,2] [3,4] [5]

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 3-4, and isolated node 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: Visit neighbors of 0: node 1, mark visited and enqueue

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

Why: We add connected nodes to explore their neighbors next

Step 3: Dequeue 1, visit neighbors: node 0 (visited), node 2 (unvisited), mark 2 visited and enqueue

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

Why: Continue exploring connected nodes to find full group

Step 4: Dequeue 2, visit neighbors: node 1 (visited), no new nodes to add

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

Why: Finished exploring first connected component

Step 5: Next unvisited node is 3, start BFS, mark visited and enqueue

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

Why: Find next connected group starting from unvisited node

Step 6: Dequeue 3, visit neighbors: node 4, mark visited and enqueue

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

Why: Explore neighbors to find full connected component

Step 7: Dequeue 4, visit neighbors: node 3 (visited), no new nodes

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

Why: Finished second connected component

Step 8: Next unvisited node is 5, start BFS, mark visited and enqueue

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

Why: Isolated node forms its own connected component

Step 9: Dequeue 5, no neighbors to visit

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

Why: Finished last connected component

Result:

Components: [[0,1,2],[3,4],[5]]

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

// Graph represents an undirected graph using adjacency list
type Graph struct {
	adjacency map[int][]int
	nodes     int
}

// NewGraph creates a graph with n nodes
func NewGraph(n int) *Graph {
	return &Graph{adjacency: make(map[int][]int), nodes: n}
}

// AddEdge adds an undirected edge between u and v
func (g *Graph) AddEdge(u, v int) {
	g.adjacency[u] = append(g.adjacency[u], v)
	g.adjacency[v] = append(g.adjacency[v], u)
}

// BFSConnectedComponents finds all connected components using BFS
func (g *Graph) BFSConnectedComponents() [][]int {
	visited := make([]bool, g.nodes)
	var components [][]int

	for i := 0; i < g.nodes; i++ {
		if !visited[i] {
			component := []int{}
			queue := list.New()
			queue.PushBack(i)
			visited[i] = true

			for queue.Len() > 0 {
				front := queue.Front()
				curr := front.Value.(int)
				queue.Remove(front)

				component = append(component, curr) // add node to current component

				for _, neighbor := range g.adjacency[curr] {
					if !visited[neighbor] {
						visited[neighbor] = true
						queue.PushBack(neighbor) // enqueue unvisited neighbors
					}
				}
			}

			components = append(components, component) // add component to result
		}
	}

	return components
}

func main() {
	g := NewGraph(6)
	g.AddEdge(0, 1)
	g.AddEdge(1, 2)
	g.AddEdge(3, 4)

	components := g.BFSConnectedComponents()
	for i, comp := range components {
		fmt.Printf("Component %d: %v\n", i+1, comp)
	}
}

for i := 0; i < g.nodes; i++ { if !visited[i] {

start BFS from each unvisited node to find new connected component

queue := list.New(); queue.PushBack(i); visited[i] = true

initialize queue and mark start node visited

for queue.Len() > 0 { front := queue.Front(); curr := front.Value.(int); queue.Remove(front)

dequeue current node to explore its neighbors

component = append(component, curr)

add current node to current connected component

for _, neighbor := range g.adjacency[curr] { if !visited[neighbor] { visited[neighbor] = true; queue.PushBack(neighbor) } }

enqueue all unvisited neighbors to continue BFS

components = append(components, component)

add completed connected component to result list

Output

Component 1: [0 1 2]

Component 2: [3 4]

Component 3: [5]

Complexity Analysis

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

Space: O(V) for visited array and queue to store nodes during BFS

vs Alternative: Compared to DFS, BFS has similar time and space complexity but explores neighbors level by level

Edge Cases

Graph with no edges (all isolated nodes)

Each node forms its own connected component

DSA Go

if !visited[i] {

Graph with a single node

Returns one component containing that single node

DSA Go

if !visited[i] {

Graph with all nodes connected (one big component)

Returns one component containing all nodes

DSA Go

for queue.Len() > 0 {

When to Use This Pattern

When you need to find groups of connected nodes in a graph, use BFS to explore neighbors level by level and collect each connected component.

Common Mistakes

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

Mistake: Starting BFS only once misses other disconnected components
Fix: Run BFS from every unvisited node to find all components

Summary

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

Use when you want to identify separate connected parts in an undirected graph.

The key insight is to explore neighbors level by level and mark visited nodes to avoid repeats.

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