BFS Breadth First Search on Graph in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 'A' in the given graph?

DSA Python

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([n for n in graph[node] if n not in visited and n not in queue])
    return visited

print(bfs(graph, 'A'))

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

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

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

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

💡 Hint

Remember BFS visits neighbors level by level, left to right as they appear in adjacency list.

BFS starts at 'A', visits neighbors 'B' and 'C' in order, then visits neighbors of 'B' ('D', 'E'), then neighbors of 'C' ('F'). The order is ['A', 'B', 'C', 'D', 'E', 'F'].

🧠 Conceptual

intermediate

Number of nodes visited in BFS

Given a graph with 7 nodes where BFS starts at node '1' and visits all reachable nodes, how many nodes will BFS visit if the graph is disconnected and only nodes 1, 2, 3 are connected?

A 4

B 3

C 7

D 0

💡 Hint

BFS only visits nodes reachable from the start node.

Since only nodes 1, 2, 3 are connected and BFS starts at 1, it visits these 3 nodes only. The other nodes are disconnected and not visited.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will this BFS code produce when run on a graph with cycles?

DSA Python

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

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'))

A Correct output: ['A', 'B', 'C']

B KeyError because of missing node

C TypeError due to wrong data type

D Infinite loop (no termination)

💡 Hint

Check how visited nodes are tracked before adding neighbors.

The code adds neighbors without checking if they are visited, causing repeated additions and an infinite loop in cyclic graphs.

❓ Predict Output

advanced

BFS traversal order with weighted graph ignoring weights

What is the BFS traversal order starting from node 1 in the weighted graph (weights ignored)?

DSA Python

graph = {
    1: [2, 3],
    2: [4],
    3: [4, 5],
    4: [6],
    5: [],
    6: []
}

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([n for n in graph[node] if n not in visited and n not in queue])
    return visited

print(bfs(graph, 1))

A [1, 2, 3, 4, 5, 6]

B [1, 3, 2, 5, 4, 6]

C [1, 2, 3, 5, 4, 6]

D [1, 3, 2, 4, 5, 6]

💡 Hint

BFS visits neighbors in the order they appear in adjacency list.

Starting at 1, neighbors 2 and 3 are visited in order, then neighbors of 2 (4), then neighbors of 3 (4 and 5), but 4 is already visited, so 5 is added, then neighbors of 4 (6). The order is [1, 2, 3, 4, 5, 6].

🚀 Application

expert

Shortest path length using BFS in unweighted graph

Given the graph below, what is the shortest path length from node 'S' to node 'G' using BFS?

DSA Python

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

from collections import deque

def bfs_shortest_path_length(graph, start, goal):
    visited = set()
    queue = deque([(start, 0)])  # (node, distance)
    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append((neighbor, dist + 1))
    return -1

print(bfs_shortest_path_length(graph, 'S', 'G'))

A 3

B 4

C 2

D 1

💡 Hint

BFS finds shortest path in unweighted graphs by level order traversal.

The shortest path from 'S' to 'G' is S -> B -> D -> G or S -> B -> E -> G, both length 2 edges away from S.

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