Shortest Path in Unweighted Graph Using BFS in DSA Java - 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 level by level, the first time it reaches the destination node, it has found the shortest path in terms of number of edges.

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 are discovered.

intermediate

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

We store the parent or predecessor of each node visited, so after reaching the destination, we can backtrack to the start node to reconstruct the path.

intermediate

What is the time complexity of BFS when finding 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, because each node and edge is processed once.

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

A Hash Map

B Stack

C Priority Queue

D Queue

BFS uses a queue to explore nodes level by level.

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

A It uses weights to calculate shortest distance

B It explores nodes in order of increasing distance from the start

C It explores nodes randomly

D It uses recursion to find paths

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

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

A Number of edges in graph

B Distance from start only

C Parent of each node

D Visited nodes count

Storing the parent of each node allows backtracking to reconstruct the path.

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

A O(V + E)

B O(V^2)

C O(E^2)

D O(log V)

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

Which of these graphs is BFS NOT guaranteed to find the shortest path in?

A Weighted graph with different weights

B Unweighted graph

C Weighted graph with equal weights

D Undirected graph

BFS does not consider edge weights, so it may not find shortest paths in weighted graphs with different weights.

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

Think about how BFS explores neighbors and how to remember the path.

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

How do you trace back from the end to the start?

Practice

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

easy

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

B. The node with the highest degree

C. The longest path between two nodes

D. The total number of edges in the graph

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 A

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 works only for weighted graphs

2. Which Java data structure is commonly used to implement BFS for shortest path in an unweighted graph?

easy

A. Queue

B. PriorityQueue

C. HashMap

D. Stack

Solution

1. Step 1: Recall BFS traversal order

   BFS explores nodes in a first-in, first-out order to visit neighbors level by level.

2. Step 2: Identify the correct data structure

   A Queue supports FIFO order, making it ideal for BFS traversal.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   BFS uses Queue for level order traversal [OK]

Hint: Use Queue for FIFO order in BFS traversal [OK]

Common Mistakes:

• Using Stack which is LIFO and suits DFS
• Confusing PriorityQueue with Queue
• Using HashMap which stores key-value pairs, not order

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

Graph edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4

Assume nodes are 0 to 4 and distance to start node is 0.

medium

A. [0, 0, 0, 0, 0]

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

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

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

Solution

1. Step 1: Start BFS from node 0 and set distance 0

   Distance[0] = 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

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

3. Step 3: Visit neighbor of 3

   Node 4 is neighbor of 3, distance is 3.

4. Final Answer:

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

5. Quick Check:

   Distances increase by 1 per BFS level [OK]

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

Common Mistakes:

• Assigning wrong distances to node 3
• Confusing BFS with DFS distances
• Setting all distances to zero

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

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<Integer> q = new LinkedList<>();
q.add(start);
dist[start] = 0;
while(!q.isEmpty()) {
  int u = q.poll();
  for(int v : graph.get(u)) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.add(v);
    }
  }
}

medium

A. The queue should be a Stack for BFS

B. Distance array should be initialized with zeros

C. The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead

D. The start node distance should be Integer.MAX_VALUE

Solution

1. Step 1: Understand distance initialization

   Distances are set to Integer.MAX_VALUE to mark unvisited nodes.

2. Step 2: Check visitation condition

   Condition 'dist[v] == 0' wrongly checks for zero, but unvisited nodes have Integer.MAX_VALUE.

3. Step 3: Correct condition

   Change condition to 'dist[v] == Integer.MAX_VALUE' to detect unvisited nodes properly.

4. Final Answer:

   The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead -> Option C

5. Quick Check:

   Check unvisited nodes by Integer.MAX_VALUE [OK]

Hint: Check unvisited nodes by initial max distance, not zero [OK]

Common Mistakes:

• Using zero to check unvisited nodes when distances initialized to max
• Using Stack instead of Queue for BFS
• Incorrect distance initialization

5. Given an unweighted graph with nodes 0 to 5 and edges:

0-1, 0-2, 1-3, 2-3, 3-4, 4-5

If BFS starts at node 0, what is the shortest path from node 0 to node 5?

hard

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

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

C. [0, 2, 3, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Run BFS to find shortest distances

   Distances: 0->0, 1->1, 2->1, 3->2, 4->3, 5->4.

2. Step 2: Trace shortest path from 5 back to 0

   From 5 to 4, 4 to 3, 3 to 1 or 2, choose 1 for shortest path: 0->1->3->4->5.

3. Final Answer:

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

4. Quick Check:

   Shortest path follows BFS layers [OK]

Hint: Trace path backward from target using distances [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS distances
• Skipping nodes in path
• Confusing BFS with DFS path