BFS Breadth First Search on Graph in DSA Typescript - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark node visited

↓

Add node neighbors to queue

↓

Dequeue next node

↓

If queue empty?

Yes→End

No↓

Repeat process for next node

Start from a node, visit it, add neighbors to a queue, then visit nodes in queue order until all reachable nodes are visited.

Execution Sample

DSA Typescript

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

This code visits nodes in a graph starting from 'start' using BFS, tracking visited nodes and queueing neighbors.

Execution Table

Step	Current Node	Visited Set	Queue	Action	Graph State
1	A	{}	[A]	Start with node A in queue	Graph: A->B,C; B->A,D; C->A,D; D->B,C,E; E->D
2	A	{A}	[B,C]	Visit A, add neighbors B,C to queue	Graph unchanged
3	B	{A,B}	[C,D]	Visit B, add neighbor D to queue	Graph unchanged
4	C	{A,B,C}	[D]	Visit C, add neighbor D (already in queue) skipped	Graph unchanged
5	D	{A,B,C,D}	[E]	Visit D, add neighbor E to queue	Graph unchanged
6	E	{A,B,C,D,E}	[]	Visit E, no new neighbors	Graph unchanged
7	-	{A,B,C,D,E}	[]	Queue empty, BFS ends	Graph unchanged

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
visited	{}	{A}	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C,D,E}	{A,B,C,D,E}
queue	[A]	[B,C]	[C,D]	[D]	[E]	[]	[]
currentNode	-	A	B	C	D	E	-

Key Moments - 3 Insights

Why do we add neighbors to the queue only if they are not visited?

Because adding only unvisited neighbors prevents revisiting nodes and infinite loops, as shown in steps 3 and 4 where D is added once.

Why does BFS use a queue instead of a stack?

A queue ensures nodes are visited in order of their distance from the start node (level by level), as seen by the order nodes are dequeued in the execution table.

What happens if the graph has disconnected parts?

BFS only visits nodes reachable from the start node, so disconnected parts remain unvisited, which is why the visited set only contains connected nodes.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue content after visiting node B (Step 3)?

A [B, C]

B [D]

C [C, D]

D []

💡 Hint

Check the 'Queue' column in row for Step 3 in the execution_table.

At which step does the BFS visit node E?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'Current Node' column and find when E is visited in the execution_table.

If we start BFS from node C instead of A, which node will be visited first?

A A

B C

C B

D D

💡 Hint

BFS always starts from the given start node, see the first step in the execution_table.

Concept Snapshot

BFS (Breadth First Search) visits graph nodes level by level.
Use a queue to track nodes to visit next.
Mark nodes visited to avoid repeats.
Start from a node, enqueue neighbors, dequeue and visit.
Stops when queue is empty (all reachable nodes visited).

Full Transcript

Breadth First Search (BFS) explores a graph by visiting nodes in order of their distance from the start node. It uses a queue to keep track of nodes to visit next and a set to mark visited nodes. Starting from the source node, BFS visits it, adds its neighbors to the queue if not visited, then dequeues the next node to visit. This process repeats until the queue is empty, meaning all reachable nodes have been visited. The execution table shows each step with the current node, visited nodes, queue content, and actions taken. Key moments clarify why neighbors are only added if unvisited, why a queue is used, and what happens with disconnected graph parts. The visual quiz tests understanding of queue content, visit order, and start node effects.

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