Why BFS Breadth First Search on Graph in DSA Python?

The Big Idea

Discover how BFS saves you from getting lost in complex paths by exploring step by step!

The Scenario

Imagine you are in a huge maze and want to find the shortest path to the exit. You try to explore every path one by one, going deep into one path before checking others. This can take a very long time and you might get lost or miss the shortest way out.

The Problem

Manually exploring paths deeply means you might waste time going down long dead ends first. It is easy to forget which paths you already checked, and you might repeat the same steps again and again. This makes finding the shortest path slow and confusing.

The Solution

BFS (Breadth First Search) helps by exploring all paths step by step, level by level. It checks all neighbors first before going deeper. This way, BFS finds the shortest path quickly and avoids repeating steps, making the search organized and efficient.

Before vs After

✗ Before

def find_path(graph, start, end):
    # Deep search manually
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node == end:
            return True
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return False

✓ After

from collections import deque

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

What It Enables

BFS enables finding the shortest path in a graph quickly and reliably by exploring neighbors level by level.

Real Life Example

When you use a GPS app to find the shortest route from your home to a store, BFS helps the app check all nearby roads first before looking further, ensuring you get the fastest route.

Key Takeaways

BFS explores graph nodes level by level, not deeply.

It finds shortest paths efficiently.

It avoids repeating nodes by tracking visited ones.

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