Shortest Path in Unweighted Graph Using BFS in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Shortest Path Distance Array

What is the output of the distance array after running BFS from node 0 in the given graph?

DSA Java

import java.util.*;

public class Graph {
    static int V = 5;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    public static void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    public static int[] bfsShortestPath(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        dist[src] = 0;
        q.add(src);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(2, 3);
        addEdge(3, 4);

        int[] dist = bfsShortestPath(0);
        System.out.println(Arrays.toString(dist));
    }
}

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

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

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

D [0, -1, -1, -1, -1]

💡 Hint

Think about the shortest number of edges from node 0 to each node.

BFS explores neighbors level by level. From node 0, nodes 1 and 2 are at distance 1, node 3 is reached via 1 or 2 at distance 2, and node 4 is reached from 3 at distance 3.

🧠 Conceptual

intermediate

Why BFS Finds Shortest Path in Unweighted Graphs

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

A Because BFS uses a stack to explore nodes deeply first.

B Because BFS uses random traversal to find shortest paths.

C Because BFS marks nodes as visited only after exploring all neighbors.

D Because BFS explores nodes in order of increasing distance from the source.

💡 Hint

Think about the order in which BFS visits nodes.

BFS visits nodes layer by layer, so the first time it reaches a node is via the shortest path from the source.

🔧 Debug

advanced

Identify the Bug in BFS Distance Calculation

What error will occur when running this BFS code snippet for shortest path distances?

DSA Java

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

A Nodes at distance 0 will never be visited except the source, causing incorrect distances.

B The code will compile but produce negative distances.

C The queue will never be empty causing an infinite loop.

D The code will throw a NullPointerException.

💡 Hint

Consider how unvisited nodes are identified.

Using 0 to mark unvisited nodes conflicts with the source node distance 0, so other nodes with distance 0 are never visited.

🚀 Application

advanced

Find Shortest Path Length Between Two Nodes

Given an unweighted graph and two nodes, which code snippet correctly returns the shortest path length between them using BFS?

A Use BFS from source, return dist[target] immediately after first visit.

B Use DFS from source, return dist[target] after DFS completes.

C Use BFS from source, return dist[target] after BFS completes.

D Use BFS from target, return dist[source] after BFS completes.

💡 Hint

Shortest path is found when target is first reached in BFS.

In BFS, the first time the target node is visited, the shortest path length is known and can be returned immediately.

❓ Predict Output

expert

Output of BFS Path Reconstruction

What is the output path from node 0 to node 4 after running BFS with parent tracking?

DSA Java

import java.util.*;

public class GraphPath {
    static int V = 5;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    public static void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    public static List<Integer> bfsPath(int src, int dest) {
        int[] parent = new int[V];
        Arrays.fill(parent, -1);
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[V];
        visited[src] = true;
        q.add(src);

        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == dest) break;
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    q.add(v);
                }
            }
        }

        List<Integer> path = new ArrayList<>();
        if (parent[dest] == -1 && src != dest) return path;
        for (int v = dest; v != -1; v = parent[v]) {
            path.add(v);
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(2, 3);
        addEdge(3, 4);

        List<Integer> path = bfsPath(0, 4);
        System.out.println(path);
    }
}

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

B [0, 2, 3, 4]

C [0, 1, 3, 4]

D [4, 3, 1, 0]

💡 Hint

BFS finds shortest path; parent array tracks the path backwards.

BFS visits node 1 before node 2 at the first level, so the path through 1 is recorded first and reconstructed as [0,1,3,4].

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