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

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Add source to queue

↓

While queue not empty

↓

Dequeue node

↓

Visit node if not visited

↓

Add all unvisited neighbors to queue

↓

Repeat loop

BFS starts at a node, visits neighbors level by level using a queue until all reachable nodes are visited.

Execution Sample

DSA Javascript

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

This code performs BFS on a graph from a start node, visiting nodes level by level.

Execution Table

Step	Operation	Current Node	Visited Set	Queue	Action	Graph State
1	Initialize	None	{}	[A]	Start with node A in queue	Graph: A->B,C; B->A,D; C->A,D; D->B,C,E; E->D,F; F->E
2	Dequeue	A	{}	[]	Visit A, add to visited	Visited: {A}
3	Enqueue neighbors	A	{A}	[B,C]	Add B and C to queue	Queue: [B,C]
4	Dequeue	B	{A}	[C]	Visit B, add to visited	Visited: {A,B}
5	Enqueue neighbors	B	{A,B}	[C,D]	Add D to queue (A visited)	Queue: [C,D]
6	Dequeue	C	{A,B}	[D]	Visit C, add to visited	Visited: {A,B,C}
7	Enqueue neighbors	C	{A,B,C}	[D]	Neighbors A,D visited, add none	Queue: [D]
8	Dequeue	D	{A,B,C}	[]	Visit D, add to visited	Visited: {A,B,C,D}
9	Enqueue neighbors	D	{A,B,C,D}	[E]	Add E to queue (B,C visited)	Queue: [E]
10	Dequeue	E	{A,B,C,D}	[]	Visit E, add to visited	Visited: {A,B,C,D,E}
11	Enqueue neighbors	E	{A,B,C,D,E}	[F]	Add F to queue (D visited)	Queue: [F]
12	Dequeue	F	{A,B,C,D,E}	[]	Visit F, add to visited	Visited: {A,B,C,D,E,F}
13	Enqueue neighbors	F	{A,B,C,D,E,F}	[]	Neighbor E visited, add none	Queue: []
14	End	None	{A,B,C,D,E,F}	[]	Queue empty, BFS complete	All nodes visited

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
visited	{}	{A}	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C,D,E}	{A,B,C,D,E,F}	{A,B,C,D,E,F}
queue	[A]	[]	[C,D]	[D]	[E]	[F]	[]	[]
current node	None	A	B	C	D	E	F	None

Key Moments - 3 Insights

Why do we check if a node is visited before adding neighbors to the queue?

To avoid adding the same node multiple times and prevent infinite loops. See steps 5 and 7 where neighbors already visited are not added again.

Why do we use a queue instead of a stack?

A queue ensures nodes are visited in the order they are discovered, level by level. This is shown by the queue growing and shrinking in FIFO order in the execution_table.

What happens if the graph has disconnected parts?

BFS only visits nodes reachable from the start node. Nodes in disconnected parts remain unvisited, as the queue empties without reaching them.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue content after step 5?

A [C,D]

B [B,C,D]

C [D]

D []

💡 Hint

Check the 'Queue' column in row for step 5 in execution_table

At which step does node D get visited?

A Step 6

B Step 8

C Step 10

D Step 12

💡 Hint

Look at 'Current Node' and 'Visited Set' columns in execution_table

If node E was not connected to D, what would happen to the queue after step 9?

A Queue would contain [E]

B Queue would contain [F]

C Queue would be empty

D Queue would contain [D]

💡 Hint

Refer to step 9 enqueue neighbors action and what happens if no neighbors are added

Concept Snapshot

BFS uses a queue to visit nodes level by level.
Start by adding the start node to the queue.
Dequeue a node, visit it, then enqueue all unvisited neighbors.
Repeat until the queue is empty.
Ensures shortest path in unweighted graphs.
Avoid revisiting nodes by tracking visited set.

Full Transcript

Breadth First Search (BFS) explores a graph starting from a source node. It uses a queue to keep track of nodes to visit next. Initially, the start node is added to the queue. Then, while the queue is not empty, the algorithm removes the front node, visits it if not already visited, and adds all its unvisited neighbors to the queue. This process continues until all reachable nodes are visited. BFS visits nodes in layers, ensuring nodes closer to the start are visited first. The visited set prevents revisiting nodes and infinite loops. The queue operates in FIFO order, which is essential for BFS behavior. If the graph has disconnected parts, BFS only visits the connected component containing the start node.

Practice

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

easy

A. A stack to explore nodes deeply first

B. A hash map to store visited nodes only

C. A queue to explore nodes level by level

D. A priority queue to explore nodes by weight

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, so it needs to remember nodes in the order they are discovered.

2. Step 2: Identify the data structure for order

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

3. Final Answer:

   A queue to explore nodes level by level -> Option C

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses queue, DFS uses stack [OK]

Common Mistakes:

• Confusing BFS with DFS and choosing stack
• Thinking BFS uses priority queue
• Ignoring the order of node visits

2. Which of the following is the correct syntax to enqueue a node `v` into a queue named `queue` in JavaScript?

easy

A. queue.push(v);

B. queue.enqueue(v);

C. queue.add(v);

D. queue.insert(v);

Solution

1. Step 1: Recall JavaScript array methods for queue

   JavaScript arrays use `push()` to add elements at the end, simulating enqueue.

2. Step 2: Verify other options

   Methods like `enqueue()`, `add()`, or `insert()` are not standard array methods in JavaScript.

3. Final Answer:

   queue.push(v); -> Option A

4. Quick Check:

   Enqueue in JS array = push() [OK]

Hint: Use push() to add at queue's end in JS [OK]

Common Mistakes:

• Using non-existent enqueue() method
• Confusing push() with pop()
• Trying to use add() or insert() which don't exist

3. Consider the following graph represented as adjacency list:

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

function bfs(start) {
  const queue = [start];
  const visited = new Set([start]);
  const order = [];

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

console.log(bfs(1));

What will be the output printed?

medium

A. [1, 3, 2, 4]

B. [1, 2, 3, 4]

C. [1, 4, 2, 3]

D. [4, 2, 3, 1]

Solution

1. Step 1: Start BFS from node 1

   Queue = [1], visited = {1}, order = []. Dequeue 1, order = [1]. Enqueue neighbors 2 and 3.

2. Step 2: Visit nodes in queue order

   Queue = [2,3]. Dequeue 2, order = [1,2]. Enqueue neighbor 4. Queue = [3,4]. Dequeue 3, order = [1,2,3]. Neighbor 4 already visited, skip. Dequeue 4, order = [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option B

4. Quick Check:

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

Hint: BFS visits neighbors in queue order [OK]

Common Mistakes:

• Mixing order of neighbors
• Not marking visited before enqueue
• Using stack behavior instead of queue

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

function bfs(start, graph) {
  const queue = [start];
  const visited = new Set();
  const order = [];

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

medium

A. Visited nodes are not marked before enqueueing, causing duplicates

B. Visited set is never updated, causing infinite loop

C. Visited nodes are marked after enqueueing, causing duplicates

D. Queue is not initialized properly

Solution

1. Step 1: Check order of visited marking

   Visited nodes are marked after enqueueing neighbors, which can cause duplicates if neighbors appear multiple times.

2. Step 2: Correct approach

   Mark nodes as visited before enqueueing to avoid adding duplicates to the queue.

3. Final Answer:

   Visited nodes are not marked before enqueueing, causing duplicates -> Option A

4. Quick Check:

   Mark visited before enqueue = no duplicates [OK]

Hint: Mark visited before enqueue to avoid duplicates [OK]

Common Mistakes:

• Marking visited after enqueue
• Not marking visited at all
• Initializing queue incorrectly

5. Given a graph with nodes and edges, how can BFS be adapted to find the shortest path length from a start node to a target node? Choose the best approach.

hard

A. Use a stack to explore nodes and update shortest distance dynamically

B. Use DFS and record path length when target is found

C. Use BFS but do not track visited nodes to find all paths

D. Use BFS with a queue and track distance for each node when first visited

Solution

1. Step 1: Understand BFS property for shortest path

   BFS explores nodes level by level, so the first time we reach the target node is the shortest path.

2. Step 2: Track distance during BFS

   Maintain a distance map or array, updating distance when a node is first visited to record shortest path length.

3. Final Answer:

   Use BFS with a queue and track distance for each node when first visited -> Option D

4. Quick Check:

   BFS + distance tracking = shortest path [OK]

Hint: Track distance on first visit in BFS for shortest path [OK]

Common Mistakes:

• Using DFS which may not find shortest path
• Not tracking visited nodes causing infinite loops
• Using stack instead of queue for BFS