BFS traversal and applications in Data Structures Theory - Time & Space Complexity

Time Complexity: BFS traversal and applications

O(n + m)

Understanding Time Complexity

We want to understand how the time needed for BFS traversal grows as the graph gets bigger.

Specifically, how does BFS handle more nodes and edges in a graph?

Scenario Under Consideration

Analyze the time complexity of the following BFS traversal code.

function BFS(graph, startNode) {
  let queue = []
  let visited = new Set()
  queue.push(startNode)
  visited.add(startNode)

  while (queue.length > 0) {
    let node = queue.shift()
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
}
    

This code visits all nodes reachable from the startNode using a queue, exploring neighbors level by level.

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 enqueued and dequeued once; each edge is checked once.

How Execution Grows With Input

As the number of nodes and edges grows, BFS visits each node once and checks all edges once.

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

Pattern observation: Operations grow roughly in proportion to nodes plus 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 time proportional to n squared because it checks all pairs of nodes."

[OK] Correct: BFS only checks edges that actually exist, not all pairs of nodes, so it depends on edges, not all possible pairs.

Interview Connect

Understanding BFS time complexity helps you explain how graph algorithms scale and why BFS is efficient for many 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 is the main data structure used in BFS (Breadth-First Search) traversal of a graph?

easy

A. Queue

B. Stack

C. Priority Queue

D. Hash Map

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, which requires processing nodes in the order they are discovered.

2. Step 2: Identify the suitable data structure

   A queue follows First-In-First-Out (FIFO) order, perfect for level-wise exploration in BFS.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   BFS uses a queue = Queue [OK]

Hint: BFS uses FIFO order, so it needs a queue [OK]

Common Mistakes:

• Confusing BFS with DFS which uses a stack
• Thinking BFS uses a priority queue
• Assuming BFS uses a hash map as main structure

2. Which of the following is the correct way to mark a node as visited in BFS to avoid revisiting it?

easy

A. Add node to a stack after visiting

B. Add node to a visited set or list immediately when enqueued

C. Add node to the queue only after processing all neighbors

D. Do not mark nodes; revisit all nodes

Solution

1. Step 1: Understand when to mark nodes visited in BFS

   Nodes should be marked visited when they are enqueued to prevent multiple enqueues of the same node.

2. Step 2: Identify correct marking method

   Adding nodes to a visited set immediately when enqueued ensures no duplicates in the queue.

3. Final Answer:

   Add node to a visited set or list immediately when enqueued -> Option B

4. Quick Check:

   Mark visited on enqueue = Add node to a visited set or list immediately when enqueued [OK]

Hint: Mark nodes visited when enqueued, not after dequeued [OK]

Common Mistakes:

• Marking nodes visited only after dequeuing
• Using a stack instead of a visited set
• Not marking nodes visited at all

3. Consider the following graph edges:
0 - 1, 0 - 2, 1 - 3, 2 - 3
If BFS starts at node 0, what is the order of nodes visited?

medium

A. [0, 1, 2, 3]

B. [0, 2, 1, 3]

C. [0, 3, 1, 2]

D. [1, 0, 2, 3]

Solution

1. Step 1: Start BFS from node 0

   Enqueue 0, visited order starts with 0.

2. Step 2: Enqueue neighbors of 0 in order

   Neighbors are 1 and 2, enqueue 1 then 2.

3. Step 3: Dequeue 1 and enqueue its neighbor 3

   3 is neighbor of 1, enqueue 3.

4. Step 4: Dequeue 2, neighbor 3 already visited

   No new nodes added.

5. Step 5: Dequeue 3, no new neighbors

   Traversal ends.

6. Final Answer:

   [0, 1, 2, 3] -> Option A

7. Quick Check:

   BFS order = [0, 1, 2, 3] [OK]

Hint: Visit neighbors in order they appear, enqueue before dequeue [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Adding nodes multiple times
• Starting BFS from wrong node

4. The following BFS code snippet has a bug. What is the error?

visited = set()
queue = [start]
visited.add(start)
while queue:
    node = queue.pop()
    for neighbor in graph[node]:
        if neighbor not in visited:
            queue.append(neighbor)
            visited.add(neighbor)

medium

A. Not marking start node as visited before loop

B. Queue should be a stack for BFS

C. Visited nodes added after enqueueing neighbors

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

Solution

1. Step 1: Analyze queue operations

   pop() without argument removes last element, making it LIFO (stack), not FIFO (queue).

2. Step 2: Understand BFS requires FIFO

   BFS needs to remove from front (pop(0)) to process nodes level by level.

3. Final Answer:

   Using pop() removes from the end, causing DFS behavior -> Option D

4. Quick Check:

   pop() without index = DFS, not BFS [OK]

Hint: Use pop(0) for queue behavior in BFS [OK]

Common Mistakes:

• Using pop() instead of pop(0)
• Forgetting to mark start node visited
• Confusing stack and queue roles

5. You want to find the shortest path in an unweighted graph from node A to node B using BFS. Which of the following modifications is necessary to track the actual path?

hard

A. Run BFS twice, once from A and once from B, then combine results

B. Use a stack instead of a queue to track the path

C. Store each node's parent when enqueuing it, then backtrack from B to A

D. Mark nodes visited only after dequeuing them

Solution

1. Step 1: Understand BFS finds shortest path length

   BFS explores nodes level by level, so the first time B is found is shortest path length.

2. Step 2: Track path by storing parents

   When a node is enqueued, record which node led to it (its parent). After BFS, backtrack from B to A using parents.

3. Final Answer:

   Store each node's parent when enqueuing it, then backtrack from B to A -> Option C

4. Quick Check:

   Parent tracking + backtrack = shortest path [OK]

Hint: Save parents on enqueue, backtrack from target [OK]

Common Mistakes:

• Using stack instead of queue for BFS
• Marking visited too late causing duplicates
• Running BFS twice unnecessarily