Shortest Path in Unweighted Graph Using BFS in DSA Python - Execution Trace

Concept Flow - Shortest Path in Unweighted Graph Using BFS

Start at source node

↓

Initialize queue with source

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor of current

↓

If neighbor not visited

↓

Mark visited, set distance, enqueue

↓

Repeat until all reachable nodes processed

↓

Shortest distances from source ready

Start from the source node, explore neighbors level by level using a queue, marking distances as you go until all reachable nodes are processed.

Execution Sample

DSA Python

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

# BFS shortest path from 'A'

This code finds shortest distances from node 'A' to all other nodes in an unweighted graph using BFS.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Map	Action
1	Initialize	-	['A']	{}	{'A': 0}	Start BFS from 'A' with distance 0
2	Dequeue	A	[]	{'A'}	{'A': 0}	Visit neighbors B, C; mark visited, set distance 1, enqueue
3	Enqueue neighbors	-	['B', 'C']	{'A', 'B', 'C'}	{'A': 0, 'B': 1, 'C': 1}	Add B and C to queue
4	Dequeue	B	['C']	{'A', 'B', 'C'}	{'A': 0, 'B': 1, 'C': 1}	Visit neighbors A, D; A visited, D not visited
5	Enqueue neighbor	-	['C', 'D']	{'A', 'B', 'C', 'D'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2}	Add D to queue with distance 2
6	Dequeue	C	['D']	{'A', 'B', 'C', 'D'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2}	Visit neighbors A, D; both visited, no enqueue
7	Dequeue	D	[]	{'A', 'B', 'C', 'D'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2}	Visit neighbors B, C, E; B,C visited, E not visited
8	Enqueue neighbor	-	['E']	{'A', 'B', 'C', 'D', 'E'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}	Add E to queue with distance 3
9	Dequeue	E	[]	{'A', 'B', 'C', 'D', 'E'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}	Visit neighbor D; already visited, no enqueue
10	Queue empty	-	[]	{'A', 'B', 'C', 'D', 'E'}	{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}	All reachable nodes processed, BFS ends

💡 Queue is empty, all reachable nodes visited, shortest distances computed

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	Final
Queue	['A']	['B', 'C']	['C', 'D']	['E']	[]
Visited Set	{}	{'A', 'B', 'C'}	{'A', 'B', 'C', 'D'}	{'A', 'B', 'C', 'D', 'E'}	{'A', 'B', 'C', 'D', 'E'}
Distance Map	{'A': 0}	{'A': 0, 'B': 1, 'C': 1}	{'A': 0, 'B': 1, 'C': 1, 'D': 2}	{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}	{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}

Key Moments - 3 Insights

Why do we mark a node as visited when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see Step 3 and Step 5) prevents adding the same node multiple times to the queue, avoiding repeated processing and infinite loops.

Why does BFS guarantee the shortest path in an unweighted graph?

Because BFS explores nodes level by level (distance 0, then 1, then 2, etc.), the first time we reach a node is via the shortest path, as shown by the increasing distance values in the Distance Map.

What happens if the graph has disconnected nodes?

Nodes not reachable from the source won't be visited or added to the Distance Map, so their distances remain undefined, as BFS only processes reachable nodes.

Visual Quiz - 3 Questions

Look at the execution table at Step 5. What is the distance assigned to node 'D'?

A 1

B 2

C 3

D 0

💡 Hint

Check the Distance Map column at Step 5 in the execution table.

At which step does the queue become empty, ending the BFS?

A Step 9

B Step 10

C Step 8

D Step 7

💡 Hint

Look at the Queue State column and the Action description in the execution table.

If we forget to mark nodes as visited when enqueuing, what will happen?

A Nodes may be enqueued multiple times, causing repeated processing.

B The BFS will run faster.

C Distances will be incorrect but no repeated nodes.

D The queue will never empty.

💡 Hint

Refer to the key moment about when nodes are marked visited and the queue state changes.

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue starting from source node
- Mark nodes visited when enqueued
- Distance to source = 0
- Distance to neighbors = distance to current + 1
- BFS explores nodes level by level
- First visit to node gives shortest path distance

Full Transcript

This visualization shows how BFS finds shortest paths in an unweighted graph. We start from the source node, add it to a queue, and mark its distance as zero. Then, we repeatedly dequeue nodes, visit their neighbors, and enqueue unvisited neighbors while marking their distance as one more than the current node. We mark nodes as visited when enqueuing to avoid repeats. The process continues until the queue is empty, meaning all reachable nodes have their shortest distances recorded. The execution table tracks each step, queue contents, visited nodes, and distance map updates. Key moments clarify why marking visited on enqueue is important, why BFS guarantees shortest paths, and what happens with disconnected nodes. The quiz tests understanding of distances, queue emptying, and visited marking. This method ensures shortest paths in unweighted graphs efficiently.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The shortest path from a start node to all other nodes

B. The longest path in the graph

C. The node with the highest degree

D. The cycle in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of distance, it finds the shortest path to each node.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option A

4. Quick Check:

   BFS = Shortest path in unweighted graph [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS works only for weighted graphs

2. Which Python data structure is best to implement the queue needed for BFS?

easy

A. list with append() and pop(0)

B. collections.deque for efficient pops from front

C. set to store unique nodes

D. dictionary to map nodes to distances

Solution

1. Step 1: Identify queue operations in BFS

   BFS requires adding to the back and removing from the front efficiently.

2. Step 2: Choose data structure with O(1) pops from front

   collections.deque supports fast append and popleft operations, unlike list pop(0) which is slow.

3. Final Answer:

   collections.deque for efficient pops from front -> Option B

4. Quick Check:

   Use deque for BFS queue [OK]

Hint: Use deque for fast queue operations in BFS [OK]

Common Mistakes:

• Using list pop(0) causing slow performance
• Using set which is unordered
• Using dict which is not a queue

3. What is the output distance list after running BFS from node 0 on this graph?

graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

medium

A. [0, 2, 2, 3]

B. [1, 0, 1, 2]

C. [0, 1, 1, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance to 0 is 0, others are infinity initially.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0 are 1 and 2, distance 1 each. Then neighbor of 1 is 3, distance 2.

3. Final Answer:

   [0, 1, 1, 2] -> Option C

4. Quick Check:

   Distances = [0,1,1,2] [OK]

Hint: Distance increments by 1 per BFS level [OK]

Common Mistakes:

• Mixing node indices with distances
• Assigning wrong distances to neighbors
• Forgetting to update distances only once

4. Identify the bug in this BFS code snippet for shortest path:

def bfs(graph, start):
    from collections import deque
    queue = deque([start])
    distances = {start: 0}
    while queue:
        node = queue.pop()
        for neighbor in graph[node]:
            if neighbor not in distances:
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances

medium

A. Using queue.pop() instead of queue.popleft() causes wrong order

B. Distances dictionary should be a list

C. Neighbors should be checked before popping from queue

D. Start node distance should be -1

Solution

1. Step 1: Check queue operations in BFS

   BFS requires removing from front (FIFO), but pop() removes from end (LIFO).

2. Step 2: Identify correct method to remove front element

   queue.popleft() removes from front, preserving BFS order.

3. Final Answer:

   Using queue.pop() instead of queue.popleft() causes wrong order -> Option A

4. Quick Check:

   Use popleft() for BFS queue [OK]

Hint: Use popleft() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Using pop() causing DFS-like behavior
• Confusing list and dict for distances
• Incorrect initialization of distances

5. Given a grid where 0 represents open cell and 1 represents blocked cell, how can BFS be used to find the shortest path from top-left to bottom-right?

grid = [
  [0, 0, 1],
  [1, 0, 1],
  [1, 0, 0]
]

hard

A. Use BFS only on rows, ignoring columns

B. Run DFS to explore all paths and pick shortest

C. Use BFS but ignore blocked cells as neighbors

D. Treat each cell as a node, edges connect adjacent open cells; run BFS from start to find shortest path

Solution

1. Step 1: Model grid as graph nodes and edges

   Each open cell is a node; edges connect up/down/left/right neighbors if open.

2. Step 2: Run BFS from top-left to bottom-right

   BFS finds shortest path in unweighted graph; blocked cells are excluded from edges.

3. Final Answer:

   Treat each cell as a node, edges connect adjacent open cells; run BFS from start to find shortest path -> Option D

4. Quick Check:

   Grid BFS = shortest path via open neighbors [OK]

Hint: Model grid as graph, BFS finds shortest path avoiding blocks [OK]

Common Mistakes:

• Using DFS which is not shortest path
• Ignoring blocked cells incorrectly
• Not connecting neighbors properly