BFS Breadth First Search on Graph in DSA Python - Time & Space Complexity

Time Complexity: BFS Breadth First Search on Graph

O(n + m)

Understanding Time Complexity

We want to understand how the time taken by BFS changes as the graph grows.

How does BFS's work increase when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

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

This code explores all nodes reachable from the start node using BFS.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node and checking its neighbors.
• How many times: Each node is visited once; each edge is checked once.

How Execution Grows With Input

As the graph grows, BFS visits more nodes and edges.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 10 + 15 = 25 operations
100 nodes, 200 edges	About 100 + 200 = 300 operations
1000 nodes, 5000 edges	About 1000 + 5000 = 6000 operations

Pattern observation: Operations grow roughly with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + m)

This means BFS takes time proportional to the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "BFS always takes O(n²) time because it checks all pairs of nodes."

[OK] Correct: BFS only visits each node and edge once, not all pairs. So it depends on actual edges, not all possible pairs.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches scale in real problems.

Self-Check

"What if the graph is represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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