BFS Breadth First Search on Graph in DSA Python - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Add source to queue

↓

While queue not empty

↓

Dequeue node

↓

Visit node, mark visited

↓

Add unvisited neighbors to queue

↓

Repeat loop

BFS starts at a source node, visits nodes level by level using a queue, marking nodes visited and adding their neighbors to the queue until all reachable nodes are visited.

Execution Sample

DSA Python

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

def bfs(start):
    visited = set()
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited and neighbor not in queue:
                    queue.append(neighbor)

bfs('A')

Perform BFS starting from node 'A' on the given graph.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Action Description
1	Initialize	None	['A']	{}	Start BFS from 'A', add 'A' to queue
2	Dequeue	A	[]	{'A'}	Visit 'A', mark visited, enqueue neighbors 'B', 'D'
3	Enqueue	A	['B', 'D']	{'A'}	Neighbors 'B' and 'D' added to queue
4	Dequeue	B	['D']	{'A', 'B'}	Visit 'B', mark visited, enqueue neighbors 'A', 'C' (skip 'A' visited)
5	Enqueue	B	['D', 'C']	{'A', 'B'}	Neighbor 'C' added to queue
6	Dequeue	D	['C']	{'A', 'B', 'D'}	Visit 'D', mark visited, enqueue neighbors 'A', 'E' (skip 'A' visited)
7	Enqueue	D	['C', 'E']	{'A', 'B', 'D'}	Neighbor 'E' added to queue
8	Dequeue	C	['E']	{'A', 'B', 'C', 'D'}	Visit 'C', mark visited, enqueue neighbors 'B', 'F' (skip 'B' visited)
9	Enqueue	C	['E', 'F']	{'A', 'B', 'C', 'D'}	Neighbor 'F' added to queue
10	Dequeue	E	['F']	{'A', 'B', 'C', 'D', 'E'}	Visit 'E', mark visited, enqueue neighbors 'D', 'F' (skip both visited or in queue)
11	Dequeue	F	[]	{'A', 'B', 'C', 'D', 'E', 'F'}	Visit 'F', mark visited, enqueue neighbors 'C', 'E' (skip both visited)
12	End	None	[]	{'A', 'B', 'C', 'D', 'E', 'F'}	Queue empty, BFS complete

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
Queue	['A']	['B', 'D']	['D', 'C']	['C', 'E']	['E', 'F']	['F']	[]
Visited Set	{}	{'A'}	{'A', 'B'}	{'A', 'B', 'D'}	{'A', 'B', 'C', 'D'}	{'A', 'B', 'C', 'D', 'E'}	{'A', 'B', 'C', 'D', 'E', 'F'}
Current Node	None	A	B	D	C	E	F

Key Moments - 3 Insights

Why do we skip neighbors already in the visited set or queue?

Because visiting or enqueueing them again would cause repeated processing and possibly infinite loops. See steps 4, 6, 8 where neighbors already visited or in queue are skipped.

Why do we use a queue instead of a stack?

A queue ensures nodes are visited in the order they are discovered, level by level. This is shown by the queue state changing in FIFO order in the execution table.

What happens when the queue becomes empty?

It means all reachable nodes have been visited and BFS ends, as shown in step 12 where the queue is empty and BFS completes.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue state after visiting node 'D' (step 6)?

A ['C', 'E']

B ['E', 'F']

C ['B', 'D']

D ['F']

💡 Hint

Check the 'Queue State' column at step 7 in the execution table.

At which step does the BFS visit node 'F'?

A Step 9

B Step 11

C Step 10

D Step 12

💡 Hint

Look at the 'Current Node' and 'Operation' columns to find when 'F' is dequeued and visited.

If we start BFS from node 'C' instead of 'A', which node will be visited first?

A 'A'

B 'B'

C 'C'

D 'F'

💡 Hint

The BFS always starts by visiting the source node first, see step 1 where 'A' is first visited.

Concept Snapshot

BFS (Breadth First Search) explores nodes level by level.
Use a queue to track nodes to visit.
Start from source, mark visited nodes.
Dequeue node, visit it, enqueue unvisited neighbors.
Repeat until queue is empty.
Good for shortest path in unweighted graphs.

Full Transcript

Breadth First Search (BFS) starts at a chosen source node and explores all its neighbors before moving to the next level neighbors. It uses a queue to keep track of nodes to visit next. Initially, the source node is added to the queue and marked as visited. Then, while the queue is not empty, the algorithm dequeues a node, visits it, and adds all its unvisited neighbors to the queue. This process continues until the queue is empty, meaning all reachable nodes have been visited. The execution table shows each step, the current node being processed, the state of the queue, and the set of visited nodes. Key points include skipping neighbors already visited or in the queue to avoid repetition, and using a queue to ensure nodes are visited in order of discovery. BFS is useful for finding shortest paths in unweighted graphs and exploring nodes level by level.

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