Shortest Path in Unweighted Graph Using BFS in DSA Java - Deep Dive

Overview - Shortest Path in Unweighted Graph Using BFS

What is it?

The shortest path in an unweighted graph is the path with the fewest edges between two points. Breadth-First Search (BFS) is a method to explore all nodes layer by layer, starting from a source node. Using BFS, we can find the shortest path in terms of edges from the source to any other node. This method works because BFS visits nodes in increasing order of their distance from the source.

Why it matters

Without a way to find the shortest path, many real-world problems like navigation, network routing, and social connections would be inefficient or impossible to solve quickly. BFS provides a simple and reliable way to find the shortest path in unweighted graphs, which appear in many applications. Without BFS, we might waste time exploring longer paths or miss the shortest route entirely.

Where it fits

Before learning this, you should understand basic graph concepts like nodes, edges, and graph traversal. After mastering BFS for shortest paths, you can learn about weighted shortest path algorithms like Dijkstra's and A* search, which handle more complex cases.

Mental Model

Core Idea

BFS explores neighbors level by level, so the first time it reaches a node, it has found the shortest path to that node in an unweighted graph.

Think of it like...

Imagine standing in a room and shouting a message. The people closest to you hear it first, then their neighbors, and so on. The order in which people hear the message shows the shortest number of steps from you to them.

Start (S)
  │
  ├─ Level 1 neighbors
  │    ├─ Level 2 neighbors
  │    │    ├─ Level 3 neighbors
  │    │    │    ...
  BFS visits nodes in this expanding wave, guaranteeing shortest paths.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes connected by edges; unweighted means all edges count the same.

A graph is a collection of points called nodes (or vertices) connected by lines called edges. In an unweighted graph, each edge has no cost or weight, so moving from one node to another always counts as one step. For example, a social network where friendships are edges and people are nodes is an unweighted graph.

Result

You can picture a network of points connected by lines, where each connection is equal.

Understanding the structure of graphs is essential before exploring paths between nodes.

2

Foundation

What is Breadth-First Search (BFS)?

Concept: BFS explores nodes in layers, visiting all neighbors before moving deeper.

BFS starts at a chosen node and visits all its neighbors first. Then it visits neighbors of those neighbors, and so on. It uses a queue to keep track of nodes to visit next, ensuring nodes closer to the start are visited before farther ones.

Result

Nodes are visited in order of their distance from the start node.

Knowing BFS visits nodes by distance layers is key to finding shortest paths.

3

Intermediate

Tracking Distance and Paths in BFS

Concept: We can record the distance and previous node for each visited node to reconstruct shortest paths.

Along with visiting nodes, BFS keeps track of how far each node is from the start by counting edges. We also remember which node led us to the current node. This lets us build the shortest path backward once we reach the target.

Result

We get the shortest distance and can reconstruct the exact path from start to target.

Recording distances and parents during BFS turns exploration into a path-finding tool.

4

Intermediate

Implementing BFS for Shortest Path in Java

🤔Before reading on: do you think BFS alone finds the shortest path, or do we need extra data structures? Commit to your answer.

Concept: BFS uses a queue and arrays to track visited nodes, distances, and parents to find shortest paths.

We use a queue to process nodes in order. We mark nodes visited to avoid repeats. We keep an array for distances initialized to -1 (unknown). The start node distance is 0. When we visit a neighbor, if unvisited, we set its distance to current node distance + 1 and record the current node as its parent. After BFS finishes, we can reconstruct the path by following parents from target back to start.

Result

The shortest path and distance from start to target are found efficiently.

Understanding the role of each data structure in BFS clarifies how shortest paths emerge naturally.

5

Intermediate

Reconstructing the Shortest Path After BFS

🤔Before reading on: do you think the path is stored during BFS or built after? Commit to your answer.

Concept: The path is built after BFS by walking backward from target to start using parent links.

After BFS completes, we start at the target node and repeatedly look up its parent node until we reach the start. This sequence reversed gives the shortest path. If the target was never reached, no path exists.

Result

You get the exact sequence of nodes from start to target representing the shortest path.

Separating path reconstruction from BFS traversal keeps the algorithm clean and efficient.

6

Advanced

Handling Disconnected Graphs and No Path Cases

🤔Before reading on: do you think BFS always finds a path between any two nodes? Commit to your answer.

Concept: BFS only finds paths in connected parts of the graph; if no path exists, distance remains -1.

If the target node is in a different disconnected part of the graph, BFS starting from the source won't reach it. The distance array entry for the target stays -1, signaling no path. Your code should check this and handle it gracefully, for example by returning an empty path or a message.

Result

The algorithm correctly reports when no path exists instead of failing or giving wrong answers.

Recognizing graph connectivity limits BFS's reach prevents incorrect assumptions about path existence.

7

Expert

Optimizing BFS for Large Sparse Graphs

🤔Before reading on: do you think BFS performance depends more on nodes or edges? Commit to your answer.

Concept: BFS runs in O(V+E) time; using adjacency lists and early stopping improves efficiency on large graphs.

Using adjacency lists instead of matrices saves memory and speeds up neighbor lookups in sparse graphs. Also, stopping BFS as soon as the target is found avoids unnecessary work. For very large graphs, these optimizations reduce runtime and resource use significantly.

Result

BFS runs faster and uses less memory, making shortest path queries practical on big graphs.

Knowing BFS's complexity and practical optimizations is crucial for real-world applications.

Under the Hood

BFS uses a queue to explore nodes in order of increasing distance from the start. Each node is enqueued once when first discovered, ensuring the shortest path is found because the first time a node is visited is via the shortest route. The distance and parent arrays track how far and from where each node was reached. This process guarantees no node is revisited, preventing cycles and infinite loops.

Why designed this way?

BFS was designed to explore graphs layer by layer, which naturally fits shortest path discovery in unweighted graphs. Alternatives like Depth-First Search (DFS) can get stuck exploring deep paths first, missing shorter routes. BFS's queue-based approach ensures fairness and completeness. The design balances simplicity and efficiency for many graph problems.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐   enqueue neighbors
│  Queue      │─────────────▶
└──────┬──────┘              │
       │                     ▼
       │              ┌─────────────┐
       │              │ Visit Node  │
       │              └──────┬──────┘
       │                     │
       │          record distance and parent
       │                     │
       │◀────────────────────┘
       │
       ▼
  Repeat until queue empty

Myth Busters - 4 Common Misconceptions

Quick: Does BFS always find the shortest path in weighted graphs? Commit yes or no.

Common Belief: BFS finds the shortest path in any graph, weighted or unweighted.

Reality: BFS only finds shortest paths in unweighted graphs or graphs where all edges have equal weight. For weighted graphs, BFS can give wrong results.

Why it matters: Using BFS on weighted graphs can lead to incorrect paths, causing errors in routing or cost calculations.

Quick: If BFS visits a node twice, does it mean the path found is shorter the second time? Commit yes or no.

Common Belief: BFS can visit nodes multiple times to find shorter paths.

Reality: BFS visits each node only once because the first visit is always via the shortest path. Revisiting nodes is unnecessary and inefficient.

Why it matters: Revisiting nodes wastes time and can cause infinite loops if not handled properly.

Quick: Does BFS guarantee the shortest path in directed graphs? Commit yes or no.

Common Belief: BFS works the same for directed and undirected graphs for shortest paths.

Reality: BFS finds shortest paths in directed graphs as well, but only along edges following their direction. If no path exists following directions, BFS won't find one.

Why it matters: Ignoring edge direction can lead to wrong assumptions about path existence.

Quick: Is BFS always the fastest way to find shortest paths in unweighted graphs? Commit yes or no.

Common Belief: BFS is always the fastest method for shortest paths in unweighted graphs.

Reality: While BFS is efficient, in some cases bidirectional BFS (searching from both start and target simultaneously) can be faster.

Why it matters: Not knowing bidirectional BFS misses opportunities for performance gains in large graphs.

Expert Zone

1

BFS's queue ensures nodes are processed in exact order of increasing distance, which is why the first visit is always shortest.

2

Parent tracking during BFS not only helps reconstruct paths but can also be used to detect multiple shortest paths by storing multiple parents.

3

Bidirectional BFS can halve the search space by running two simultaneous BFS traversals from start and target, meeting in the middle.

When NOT to use

BFS is not suitable for weighted graphs where edges have different costs; algorithms like Dijkstra's or A* should be used instead. Also, BFS can be inefficient on very large dense graphs if memory is limited.

Production Patterns

In real systems, BFS is used for shortest path in social networks, peer-to-peer networks, and unweighted routing problems. It is often combined with heuristics or bidirectional search for performance. BFS also underpins algorithms for finding connected components and shortest path trees.

Connections

Dijkstra's Algorithm

Builds-on BFS by adding edge weights to find shortest paths in weighted graphs.

Understanding BFS's layer-by-layer search helps grasp how Dijkstra's algorithm extends this idea with priority queues to handle weights.

Queue Data Structure

BFS relies on queues to manage the order of node exploration.

Knowing how queues work clarifies why BFS visits nodes in increasing order of distance.

Wave Propagation in Physics

BFS's layer-by-layer exploration mirrors how waves spread out from a source point.

Recognizing BFS as a wave helps understand why it finds shortest paths first, similar to how light or sound reaches closest points before farther ones.

Common Pitfalls

#1 Not marking nodes as visited immediately when enqueued, causing repeated visits.

Wrong approach:

while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
queue.add(neighbor);
}
}
visited[node] = true;
}

Correct approach:

visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}

Root cause:

Delaying marking nodes visited until after dequeuing allows multiple enqueues of the same node, causing inefficiency and possible infinite loops.

#2 Using an adjacency matrix for large sparse graphs, causing high memory use and slow neighbor checks.

Wrong approach:

int[][] graph = new int[V][V]; // adjacency matrix
// BFS loops over all V nodes to find neighbors

Correct approach:

List[] graph = new ArrayList[V];
for (int i = 0; i < V; i++) graph[i] = new ArrayList<>();
// BFS loops only over actual neighbors

Root cause:

Not choosing the right graph representation leads to unnecessary work and memory waste.

#3 Reconstructing the path incorrectly by following children instead of parents.

Wrong approach:

List path = new ArrayList<>();
int current = start;
while (current != target) {
path.add(current);
current = child[current]; // incorrect
}

Correct approach:

List path = new ArrayList<>();
int current = target;
while (current != -1) {
path.add(current);
current = parent[current];
}
Collections.reverse(path);

Root cause:

Confusing direction of traversal when reconstructing path leads to wrong or incomplete paths.

Key Takeaways

BFS explores nodes in layers, guaranteeing the shortest path in unweighted graphs is found first.

Tracking distances and parents during BFS allows reconstruction of the exact shortest path.

BFS only works correctly for unweighted graphs; weighted graphs require different algorithms.

Properly marking nodes visited when enqueued prevents repeated work and infinite loops.

Optimizations like adjacency lists and bidirectional BFS improve performance on large graphs.

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