BFS Breadth First Search on Graph in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for in graph traversal?

BFS stands for Breadth First Search. It is a way to explore all nodes in a graph level by level, starting from a chosen node.

beginner

In BFS, which data structure is mainly used to keep track of nodes to visit next?

A queue is used in BFS to keep track of nodes to visit next. It helps explore nodes in the order they were discovered.

intermediate

What is the main difference between BFS and DFS (Depth First Search)?

BFS explores nodes level by level using a queue, while DFS explores as far as possible along one branch before backtracking, using a stack or recursion.

beginner

Why do we mark nodes as visited in BFS?

Marking nodes as visited prevents revisiting the same node multiple times, which avoids infinite loops and repeated work.

intermediate

What is the time complexity of BFS on a graph with V vertices and E edges?

The time complexity of BFS is O(V + E), because it visits every vertex and edge at most once.

Which data structure does BFS use to keep track of nodes to visit?

A Tree

B Queue

C Hash Map

D Stack

BFS uses a queue to explore nodes in the order they are discovered.

What is the first step in BFS starting from a node?

A Add all neighbors to the queue

B Remove the starting node from the graph

C Mark all nodes as visited

D Add the starting node to the queue and mark it visited

BFS starts by adding the starting node to the queue and marking it visited.

What happens when BFS visits a node's neighbor that is already visited?

A It skips adding it to the queue again

B It adds it again to the queue

C It removes the neighbor from the graph

D It restarts the BFS

BFS skips neighbors already visited to avoid loops and repeated visits.

Which of these is NOT true about BFS?

A It uses a stack to keep track of nodes

B It can find the shortest path in an unweighted graph

C It explores nodes level by level

D It marks nodes as visited

BFS uses a queue, not a stack, to keep track of nodes.

What is the order of visiting nodes in BFS starting from node 1 in this graph? 1 connected to 2 and 3, 2 connected to 4

A 1, 4, 2, 3

B 1, 3, 2, 4

C 1, 2, 3, 4

D 4, 2, 3, 1

BFS visits neighbors level by level: start at 1, then 2 and 3, then 4.

Explain how BFS works step-by-step on a simple graph starting from a node.

Think about how you explore friends in layers starting from one person.

Describe why BFS is useful for finding the shortest path in an unweighted graph.

Imagine walking through rooms one step at a time.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A priority queue to select nodes by weight

B. A stack to process nodes in depth order

C. A hash map to store visited nodes only

D. A queue to process nodes level by level

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, so it needs a structure that processes nodes in the order they are discovered.

2. Step 2: Identify the data structure used

   A queue follows First-In-First-Out (FIFO) order, which matches BFS's level order traversal.

3. Final Answer:

   A queue to process nodes level by level -> Option D

4. Quick Check:

   BFS uses a queue = A [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 only uses a visited set without a queue

2. Which of the following is the correct TypeScript syntax to initialize a queue for BFS using an array?

easy

A. const queue = new Queue<number>();

B. const queue: number[] = [];

C. let queue = {};

D. var queue = new ArrayQueue();

Solution

1. Step 1: Recognize TypeScript array initialization

   To create a queue using an array, declare an array with type annotation and initialize it empty.

2. Step 2: Check each option

   const queue: number[] = []; correctly declares an empty number array. const queue = new Queue<number>(); uses a class Queue which is not built-in. let queue = {}; initializes an object, not a queue. var queue = new ArrayQueue(); uses a non-existent ArrayQueue.

3. Final Answer:

   const queue: number[] = []; -> Option B

4. Quick Check:

   Array queue syntax = A [OK]

Hint: Use typed empty array for queue in TypeScript [OK]

Common Mistakes:

• Using undefined classes like Queue without import
• Initializing queue as an object {} instead of array
• Using var instead of const or let (less preferred)

3. Given the graph adjacency list below and BFS starting from node 0, what is the order of nodes visited?

const graph = {
  0: [1, 2],
  1: [3],
  2: [3],
  3: []
};

medium

A. [0, 1, 2, 3]

B. [0, 2, 1, 3]

C. [0, 3, 1, 2]

D. [1, 2, 0, 3]

Solution

1. Step 1: Start BFS from node 0

   Visit node 0 first, then enqueue its neighbors 1 and 2.

2. Step 2: Visit neighbors in queue order

   Dequeue 1, visit it, enqueue its neighbor 3. Then dequeue 2, visit it, enqueue 3 again but already visited. Finally, dequeue 3.

3. Final Answer:

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

4. Quick Check:

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

Hint: Visit nodes level by level, enqueue neighbors in order [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Visiting node 3 twice
• Starting BFS from wrong node

4. Consider this BFS code snippet in TypeScript. What is the error?

function bfs(graph: Record, start: number) {
  const queue: number[] = [start];
  const visited = new Set<number>();
  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      visited.add(node);
      for (const neighbor of graph[node]) {
        queue.push(neighbor);
      }
    }
  }
  return Array.from(visited);
}

medium

A. queue.shift() can return undefined, causing errors

B. visited set is not updated correctly

C. Neighbors are not added to queue

D. Function does not return anything

Solution

1. Step 1: Analyze queue.shift() usage

   queue.shift() returns number | undefined. If queue is empty, node can be undefined, causing errors when accessing graph[node].

2. Step 2: Identify missing check for undefined

   Code should check if node is undefined before using it. Without this, runtime error can occur.

3. Final Answer:

   queue.shift() can return undefined, causing errors -> Option A

4. Quick Check:

   Check for undefined after shift = B [OK]

Hint: Always check queue.shift() result for undefined [OK]

Common Mistakes:

• Ignoring possible undefined from shift()
• Assuming visited set is wrong when it is correct
• Thinking neighbors are not added when they are

5. You want to find the shortest path length from node 0 to node 4 in this graph using BFS:

const graph = {
  0: [1, 2],
  1: [3],
  2: [3, 4],
  3: [4],
  4: []
};

Which BFS modification helps find the shortest path length correctly?

hard

A. Ignore visited set to explore all paths

B. Use a stack instead of a queue

C. Track distance for each node when first visited

D. Visit nodes multiple times to update distance

Solution

1. Step 1: Understand BFS for shortest path

   BFS finds shortest paths in unweighted graphs by exploring neighbors level by level.

2. Step 2: Track distance when visiting nodes

   Maintain a distance map or array to record the number of edges from start node to each node when first visited.

3. Final Answer:

   Track distance for each node when first visited -> Option C

4. Quick Check:

   Distance tracking in BFS = D [OK]

Hint: Store distance on first visit to each node [OK]

Common Mistakes:

• Using stack breaks BFS order
• Visiting nodes multiple times wastes time
• Ignoring visited set causes infinite loops