Shortest Path in Unweighted Graph Using BFS in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for and what is its main use in graphs?

BFS stands for Breadth-First Search. It is mainly used to explore nodes level by level and find the shortest path in an unweighted graph.

beginner

Why is BFS suitable for finding the shortest path in an unweighted graph?

Because BFS explores neighbors in layers, the first time it reaches a node, it has found the shortest path to that node.

beginner

In BFS for shortest path, what data structure is commonly used to keep track of nodes to visit next?

A queue is used to keep track of nodes to visit next, ensuring nodes are processed in the order they were discovered.

intermediate

What additional information do we store during BFS to reconstruct the shortest path?

We store the parent or predecessor of each node to trace back the path from the destination to the source.

intermediate

What is the time complexity of BFS when used to find the shortest path in an unweighted graph?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

What data structure does BFS use to explore nodes in an unweighted graph?

A Queue

B Stack

C Priority Queue

D Hash Map

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

Why does BFS find the shortest path in an unweighted graph?

A It explores nodes randomly

B It uses weights to calculate shortest distance

C It explores nodes in increasing order of distance from the source

D It uses recursion to find paths

BFS explores nodes level by level, so the first time it reaches a node, it has found the shortest path.

What extra information is needed during BFS to reconstruct the shortest path?

A Parent of each node

B Distance from source only

C Number of neighbors

D Node color

Storing the parent of each node allows tracing back the path from destination to source.

What is the time complexity of BFS in terms of vertices (V) and edges (E)?

A O(V^2)

B O(V + E)

C O(E^2)

D O(log V)

BFS visits each vertex and edge once, so time complexity is O(V + E).

In BFS, what happens when a node is visited for the first time?

A It is processed twice

B It is ignored

C It is removed from the graph

D It is added to the queue and its distance is set

When a node is first visited, it is added to the queue and its distance and parent are recorded.

Explain how BFS can be used to find the shortest path in an unweighted graph.

Think about how BFS explores neighbors and how that helps find shortest paths.

Describe the steps to reconstruct the shortest path after BFS completes.

Parents help trace the path back from end to start.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The longest path between two nodes

B. The node with the highest degree

C. The total number of nodes in the graph

D. The shortest path from a start node to all other nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node, visiting all neighbors before moving deeper.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, the first time it reaches a node is via the shortest path.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option D

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS visits nodes by distance layers to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS counts total nodes only

2. Which JavaScript data structure is best to implement the BFS queue for shortest path?

easy

A. Map to store node distances

B. Array with push and shift methods

C. Set to store unique nodes

D. Object with key-value pairs

Solution

1. Step 1: Identify BFS queue operations

   BFS requires adding nodes at the end and removing from the front, which is a queue behavior.

2. Step 2: Use Array methods for queue

   JavaScript arrays support push (add end) and shift (remove front), perfect for BFS queue.

3. Final Answer:

   Array with push and shift methods -> Option B

4. Quick Check:

   Queue = Array push/shift [OK]

Hint: Use array push/shift for BFS queue in JavaScript [OK]

Common Mistakes:

• Using Set as queue (no order guaranteed)
• Using Map for queue operations
• Using Object which has no order

3. What is the output distance array after running BFS from node 0 on this graph?

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3]
};
// BFS from node 0

medium

A. [1, 0, 0, 1, 2]

B. [0, 1, 2, 3, 4]

C. [0, 1, 1, 2, 3]

D. [0, 2, 2, 3, 4]

Solution

1. Step 1: Initialize distances and start BFS

   Distance to start node 0 is 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

   Node 3 is neighbor of 1 and 2, so distance is 2. Node 4 is neighbor of 3, distance 3.

3. Final Answer:

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

4. Quick Check:

   Distances = [0,1,1,2,3] [OK]

Hint: Distance increments by 1 each BFS layer [OK]

Common Mistakes:

• Assigning wrong distances to neighbors
• Mixing up node indices
• Forgetting to update distance only once

4. Identify the bug in this BFS shortest path code snippet:

function bfs(graph, start) {
  const queue = [];
  const distances = {};
  queue.push(start);
  distances[start] = 0;
  while (queue.length > 0) {
    const node = queue.pop();
    for (const neighbor of graph[node]) {
      if (!(neighbor in distances)) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

medium

A. Using pop() instead of shift() causes wrong BFS order

B. Distances should be initialized with -1

C. Neighbors should be checked before pushing start node

D. Queue should be a Set to avoid duplicates

Solution

1. Step 1: Check queue operations in BFS

   BFS requires FIFO order, so nodes must be removed from front using shift(), not pop() which removes from end.

2. Step 2: Effect of using pop()

   Using pop() makes it LIFO, turning BFS into DFS order, breaking shortest path logic.

3. Final Answer:

   Using pop() instead of shift() causes wrong BFS order -> Option A

4. Quick Check:

   Queue removal must be shift() for BFS [OK]

Hint: Use shift() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Using pop() instead of shift() for queue
• Initializing distances incorrectly
• Using Set for queue which loses order

5. Given a graph with nodes 0 to 5 and edges: 0-1, 0-2, 1-3, 2-3, 3-4, 4-5, what is the shortest path from node 0 to node 5 using BFS?

hard

A. [0, 1, 3, 4, 5]

B. [0, 2, 3, 4, 5]

C. [0, 1, 2, 3, 4, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Explore neighbors from node 0

   Neighbors are 1 and 2, both distance 1.

2. Step 2: From neighbors, explore node 3

   Node 3 is neighbor of both 1 and 2, distance 2.

3. Step 3: From node 3, go to 4 then 5

   Node 4 distance 3, node 5 distance 4. The path via 1 is [0,1,3,4,5].

4. Final Answer:

   [0, 1, 3, 4, 5] -> Option A

5. Quick Check:

   Shortest path = [0,1,3,4,5] [OK]

Hint: Trace BFS layers from start to target [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Skipping nodes in path
• Confusing edges and neighbors