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.