BFS Breadth First Search on Graph in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add the starting node to the queue in BFS.

DSA Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque()
    queue.[1](start)
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

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

bfs(graph, 'A')

Drag options to blanks, or click blank then click option'

Aappendleft

Bappend

Cpush

Denqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using appendleft() instead of append()

Using non-existent methods like push or enqueue

In BFS, we add the starting node to the queue using the append() method of deque.

2fill in blank

medium

Complete the code to check if a neighbor node has been visited before adding it to the queue.

DSA Python

for neighbor in graph[node]:
    if neighbor [1] visited:
        visited.add(neighbor)
        queue.append(neighbor)

Drag options to blanks, or click blank then click option'

A==

Bin

Cnot in

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'in' instead of 'not in' causing revisits

Using equality operators instead of membership checks

We only add neighbors that are not yet visited, so we check 'if neighbor not in visited'.

3fill in blank

hard

Fix the error in the BFS loop to correctly remove the first element from the queue.

DSA Python

while queue:
    node = queue.[1]()
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

Drag options to blanks, or click blank then click option'

Apopleft

Bdequeue

Cremove

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes from the right end, causing DFS behavior

Using remove() which removes by value, not position

popleft() removes the first element from the deque, which is needed for BFS.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each node to its distance from the start node in BFS.

DSA Python

def bfs_distances(graph, start):
    distances = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distances:
                distances[neighbor] = distances[node] [1] 1
                queue.[2](neighbor)
    return distances

Drag options to blanks, or click blank then click option'

A+

B-

Cappend

Dappendleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' instead of '+' for distance calculation

Using appendleft() which changes BFS order

We add 1 to the current node's distance and append the neighbor to the queue.

5fill in blank

hard

Fill all three blanks to create a BFS function that returns the order of nodes visited as a list.

DSA Python

def bfs_order(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.[1]()
        order.[2](node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.[3](neighbor)
    return order

Drag options to blanks, or click blank then click option'

Apopleft

Bappend

Cappendleft

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() instead of popleft() changes traversal order

Using appendleft() to enqueue neighbors reverses BFS order

Use popleft() to dequeue, append() to add to order list and to enqueue neighbors.

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