BFS Breadth First Search on Graph in DSA Python

Mental Model

BFS explores all neighbors of a node before moving to the next level of nodes.

Analogy: Imagine spreading a message in a group where you tell all your friends first, then their friends, and so on, layer by layer.

Graph:
  1
 / \
2   3
|    \
4     5

Queue starts with [1] ↑

Dry Run Walkthrough

Input: Graph edges: 1-2, 1-3, 2-4, 3-5; start BFS from node 1

Goal: Visit all nodes in breadth-first order starting from node 1

Step 1: Start BFS at node 1, enqueue it and mark it visited

Queue: [1↑]
Visited: {1}

Why: We begin from the start node and mark it for visiting

Step 2: Dequeue node 1, visit it, enqueue neighbors 2 and 3 and mark them visited

Queue: [2↑, 3]
Visited: {1, 2, 3}

Why: Visit current node and add its neighbors to queue for next visits

Step 3: Dequeue node 2, visit it, enqueue neighbor 4 and mark it visited

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

Why: Continue visiting nodes level by level

Step 4: Dequeue node 3, visit it, enqueue neighbor 5 and mark it visited

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

Why: Visit all neighbors of node 1 before going deeper

Step 5: Dequeue node 4, visit it, no new neighbors

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

Why: Leaf node visited, no further nodes to add

Step 6: Dequeue node 5, visit it, no new neighbors

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

Why: All nodes visited, BFS complete

Result:

Visited order: 1 -> 2 -> 3 -> 4 -> 5

Annotated Code

DSA Python

from collections import deque

class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        if u not in self.adj:
            self.adj[u] = []
        if v not in self.adj:
            self.adj[v] = []
        self.adj[u].append(v)
        self.adj[v].append(u)  # undirected graph

    def bfs(self, start):
        visited = set()
        queue = deque()
        order = []

        queue.append(start)  # enqueue start node
        visited.add(start)   # mark start visited

        while queue:
            node = queue.popleft()  # dequeue front node
            order.append(node)      # visit node

            for neighbor in self.adj.get(node, []):
                if neighbor not in visited:
                    queue.append(neighbor)  # enqueue unvisited neighbor
                    visited.add(neighbor)   # mark neighbor visited

        return order

# Driver code

g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)

result = g.bfs(1)
print(' -> '.join(map(str, result)))

queue.append(start) # enqueue start node visited.add(start) # mark start visited

Initialize BFS by adding start node to queue and marking visited

node = queue.popleft() # dequeue front node order.append(node) # visit node

Remove node from queue and record it as visited in order

for neighbor in self.adj.get(node, []): if neighbor not in visited: queue.append(neighbor) # enqueue unvisited neighbor visited.add(neighbor) # mark neighbor visited

Add all unvisited neighbors to queue and mark them visited to avoid repeats

Output

1 -> 2 -> 3 -> 4 -> 5

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during BFS

Space: O(V) for the queue and visited set to store nodes

vs Alternative: Compared to DFS which uses stack and can go deep first, BFS uses queue to explore neighbors level by level, useful for shortest path in unweighted graphs

Edge Cases

Empty graph (no nodes)

BFS returns [start] treating it as an isolated node since start is always enqueued

DSA Python

queue.append(start)  # enqueue start node

Graph with single node and no edges

BFS visits the single node and returns it

DSA Python

for neighbor in self.adj.get(node, []):

Disconnected graph, start node in one component

BFS visits only nodes reachable from start node

DSA Python

visited.add(neighbor)   # mark neighbor visited

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest paths in unweighted graphs, BFS is the pattern to use because it visits neighbors first before going deeper.

Common Mistakes

Mistake: Not marking nodes as visited when enqueued, causing repeated visits and infinite loops
Fix: Mark nodes as visited immediately when adding to queue to prevent revisiting

Summary

BFS visits all nodes in a graph level by level starting from a given node.

Use BFS when you want to explore neighbors first or find shortest paths in unweighted graphs.

The key insight is to use a queue to keep track of nodes to visit next and mark them visited as soon as they are enqueued.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A dictionary to map nodes to their parents

B. A queue to explore nodes level by level

C. A set to store visited nodes only

D. A stack to explore nodes deeply

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To achieve level order traversal, BFS uses a queue to store nodes to visit next.

3. Final Answer:

   A queue to explore nodes level by level -> Option B

4. Quick Check:

   BFS uses queue = D [OK]

Hint: BFS uses queue for level order traversal [OK]

Common Mistakes:

• Confusing BFS with DFS which uses stack
• Thinking BFS uses only a set without queue
• Assuming BFS uses recursion instead of queue

2. Which of the following is the correct Python syntax to initialize a queue for BFS using collections module?

easy

A. queue = collections.deque()

B. queue = list()

C. queue = collections.Queue()

D. queue = set()

Solution

1. Step 1: Recall Python queue options for BFS

   Python's collections module provides deque which supports fast append and pop from both ends.

2. Step 2: Identify correct initialization

   collections.Queue() does not exist; list() is slower for queue operations; set() is unordered.

3. Final Answer:

   queue = collections.deque() -> Option A

4. Quick Check:

   Use deque for BFS queue = collections.deque() [OK]

Hint: Use collections.deque() for efficient BFS queue [OK]

Common Mistakes:

• Using list() which is slow for queue operations
• Trying collections.Queue() which is invalid
• Using set() which is unordered

3. What is the output of the following BFS traversal starting from node 'A'?

graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
}

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

print(bfs(graph, 'A'))

medium

A. ['A', 'B', 'C', 'E', 'D', 'F']

B. ['A', 'C', 'B', 'F', 'D', 'E']

C. ['A', 'B', 'C', 'D', 'E', 'F']

D. ['A', 'B', 'C', 'D', 'F', 'E']

Solution

1. Step 1: Trace BFS starting from 'A'

   Start with queue=['A'], visited=[] - Pop 'A', visited=['A'], add neighbors 'B','C' to queue - Pop 'B', visited=['A','B'], add 'D','E' - Pop 'C', visited=['A','B','C'], add 'F' - Pop 'D', visited=['A','B','C','D'], no neighbors - Pop 'E', visited=['A','B','C','D','E'], add 'F' - Pop 'F', visited=['A','B','C','D','E','F'], no neighbors

2. Step 2: Confirm order of visited nodes

   The visited order is ['A', 'B', 'C', 'D', 'E', 'F'] as BFS explores level by level.

3. Final Answer:

   ['A', 'B', 'C', 'D', 'E', 'F'] -> Option C

4. Quick Check:

   BFS order from 'A' = ['A', 'B', 'C', 'D', 'E', 'F'] [OK]

Hint: Follow queue pops and neighbor additions stepwise [OK]

Common Mistakes:

• Mixing BFS with DFS order
• Not checking if node already visited before adding
• Assuming neighbors added in wrong order

4. Identify the bug in this BFS code snippet and choose the fix:

def bfs(graph, start):
    visited = set()
    queue = [start]
    while queue:
        node = queue.pop()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])
    return list(visited)

medium

A. Change queue.pop() to queue.pop(0) to pop from front

B. Change visited to a list instead of set

C. Remove the if condition checking visited

D. Use queue.append(node) instead of extend

Solution

1. Step 1: Understand queue behavior in BFS

   BFS requires FIFO order, so nodes must be popped from the front of the queue.

2. Step 2: Identify the bug in popping nodes

   queue.pop() removes from the end (LIFO), which behaves like DFS. Changing to queue.pop(0) pops from front (FIFO).

3. Final Answer:

   Change queue.pop() to queue.pop(0) to pop from front -> Option A

4. Quick Check:

   Use pop(0) for BFS queue pop [OK]

Hint: BFS queue pops from front: use pop(0) [OK]

Common Mistakes:

• Using pop() which pops from end (DFS behavior)
• Confusing set and list for visited
• Removing visited check causing infinite loops

5. Given a graph with possible cycles, how can BFS be modified to avoid infinite loops and correctly return the shortest path length from a start node to a target node?

hard

A. Use a stack instead of queue to track nodes

B. Use DFS instead of BFS to avoid cycles

C. Remove edges that form cycles before BFS

D. Use a visited set to track visited nodes and stop when target is found, counting levels

Solution

1. Step 1: Understand BFS with cycles

   In graphs with cycles, BFS can revisit nodes infinitely unless visited nodes are tracked.

2. Step 2: Modify BFS to track visited and count levels

   Use a visited set to avoid revisiting nodes and maintain a level count to find shortest path length. Stop BFS when target node is reached.

3. Final Answer:

   Use a visited set to track visited nodes and stop when target is found, counting levels -> Option D

4. Quick Check:

   Visited set + level count = shortest path BFS [OK]

Hint: Track visited nodes and levels to avoid cycles [OK]

Common Mistakes:

• Using DFS which doesn't guarantee shortest path
• Trying to remove cycles manually before BFS
• Using stack which causes DFS behavior