Shortest Path in Unweighted Graph Using BFS in DSA Typescript - 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 level by level, which helps find this shortest path efficiently. It works by visiting neighbors first before moving deeper. This approach guarantees the shortest path in graphs where edges have no weights.

Why it matters

Without BFS, finding the shortest path in an unweighted graph could be slow and complicated, especially for large networks like social media or maps. BFS ensures we find the quickest route without unnecessary detours. This is crucial for navigation apps, network routing, and many real-world problems where speed and accuracy matter.

Where it fits

Before learning this, you should understand basic graph concepts like nodes and edges, and how BFS explores graphs. After this, you can learn shortest path algorithms for weighted graphs like Dijkstra's algorithm or A* search, which handle more complex scenarios.

Mental Model

Core Idea

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

Think of it like...

Imagine standing in a room and calling out to friends in the next rooms. You first hear from friends in rooms right next to you, then from rooms two doors away, and so on. The first time you hear from a friend, you know the shortest number of doors between you.

Start Node
  │
  ├─ Level 1 neighbors
  │    ├─ Level 2 neighbors
  │    └─ Level 2 neighbors
  └─ Level 1 neighbors

BFS visits nodes level by level, ensuring shortest paths.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of points called nodes connected by lines called edges.

A graph is a collection of nodes (also called vertices). Each node can connect to other nodes via edges. In an unweighted graph, all edges are equal; they don't have numbers or costs. For example, a friendship network where each connection is just a link without strength.

Result

You can represent relationships or connections simply as nodes and edges without extra data.

Knowing what a graph is and how nodes connect is the base for understanding any graph algorithm.

2

Foundation

What is Breadth-First Search (BFS)?

Concept: BFS explores nodes layer by layer, starting from a source node.

BFS uses a queue to visit nodes. It starts at the source node, visits all neighbors, then neighbors of neighbors, and so on. This way, it explores nodes in order of their distance from the start.

Result

You get a sequence of nodes visited in increasing order of their distance from the start node.

Understanding BFS traversal order is key to using it for shortest path finding.

3

Intermediate

Tracking Distance During BFS

Concept: We keep track of how far each node is from the start during BFS.

Along with visiting nodes, we store the distance (number of edges) from the start node. Initially, the start node has distance 0. When we visit neighbors, their distance is the current node's distance plus one.

Result

Each node gets assigned the shortest distance from the start node as BFS progresses.

Tracking distance during BFS lets us find the shortest path length without extra work.

4

Intermediate

Reconstructing the Shortest Path

Concept: We remember where each node came from to build the actual path after BFS.

Besides distance, we store the parent node for each visited node. After BFS finishes, we can follow parents backward from the target node to the start node to get the shortest path.

Result

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

Storing parents during BFS allows path reconstruction, not just distance measurement.

5

Intermediate

Implementing BFS for Shortest Path in TypeScript

🤔Before reading on: Do you think BFS needs to check all nodes or can it stop early when target is found? Commit to your answer.

Concept: BFS can stop early once the target node is found, improving efficiency.

We use a queue to hold nodes to visit. We mark nodes as visited to avoid repeats. For each node, we check neighbors. If a neighbor is unvisited, we record its distance and parent, then add it to the queue. If the neighbor is the target, we stop and reconstruct the path. Example code: function bfsShortestPath(graph: Map, start: number, target: number): number[] | null { const queue: number[] = []; const visited = new Set(); const parent = new Map(); queue.push(start); visited.add(start); while (queue.length > 0) { const node = queue.shift()!; if (node === target) { const path = []; let current = target; while (current !== start) { path.push(current); current = parent.get(current)!; } path.push(start); path.reverse(); return path; } for (const neighbor of graph.get(node) || []) { if (!visited.has(neighbor)) { visited.add(neighbor); parent.set(neighbor, node); queue.push(neighbor); } } } return null; // no path found }

Result

The function returns the shortest path as an array of nodes or null if no path exists.

Knowing BFS can stop early saves time, especially in large graphs.

6

Advanced

Handling Disconnected Graphs and No Path Cases

🤔Before reading on: If the target node is unreachable, do you think BFS returns an empty path or null? Commit to your answer.

Concept: BFS returns null when no path exists, handling disconnected graphs gracefully.

If BFS finishes without finding the target, it means no path exists. The function returns null to indicate this. This is important because some graphs have isolated parts or nodes unreachable from the start.

Result

You can detect when no path exists and handle it properly in your program.

Recognizing unreachable targets prevents incorrect assumptions about connectivity.

7

Expert

Optimizing BFS with Early Exit and Memory Efficiency

🤔Before reading on: Do you think storing parents for all nodes is always necessary for shortest path? Commit to your answer.

Concept: You can optimize BFS by stopping early and minimizing memory use by only storing parents when needed.

In very large graphs, storing parents for all nodes can be costly. If only the distance is needed, parents can be skipped. Also, stopping BFS immediately when the target is found avoids unnecessary work. Advanced implementations use bidirectional BFS, searching from both start and target to meet in the middle, cutting search time roughly in half.

Result

More efficient BFS implementations save time and memory in large-scale applications.

Understanding these optimizations helps build scalable graph algorithms for real-world systems.

Under the Hood

BFS uses a queue to explore nodes in order of their distance from the start. When a node is dequeued, all its neighbors are enqueued if unvisited. This layer-by-layer approach ensures the first time a node is visited, the shortest path to it is found. The parent map stores the path by linking each node to the node it was discovered from.

Why designed this way?

BFS was designed to explore graphs systematically without revisiting nodes, ensuring shortest paths in unweighted graphs. Alternatives like Depth-First Search (DFS) can get stuck exploring deep paths first, missing shorter routes. BFS's queue-based approach guarantees minimal edge count paths.

┌─────────────┐
│ Start Node  │
└─────┬───────┘
      │
┌─────▼───────┐
│ Queue holds │
│ nodes to    │
│ visit next  │
└─────┬───────┘
      │
┌─────▼───────┐
│ Visit node  │
│ and enqueue │
│ unvisited   │
│ neighbors   │
└─────┬───────┘
      │
┌─────▼───────┐
│ Record      │
│ distance &  │
│ parent      │
└─────────────┘

Myth Busters - 3 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 guarantees shortest paths in unweighted graphs. For weighted graphs, BFS ignores edge costs and may find longer paths.

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

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

Common Belief: BFS can visit the same node multiple times to update shortest paths.

Reality: BFS visits each node only once because the first visit is always the shortest path in unweighted graphs.

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

Quick: Can BFS find shortest paths in directed graphs the same way as undirected? Commit yes or no.

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

Reality: BFS works for both, but direction matters. Edges only go one way in directed graphs, so some nodes may be unreachable.

Why it matters: Ignoring edge direction can cause BFS to report paths that don't exist, leading to wrong conclusions.

Expert Zone

1

In large sparse graphs, adjacency lists are more efficient than adjacency matrices for BFS.

2

Bidirectional BFS can halve search time by simultaneously searching from start and target nodes.

3

Memory usage can be reduced by reconstructing paths lazily or only storing parents for nodes on the final path.

When NOT to use

BFS is not suitable for graphs with weighted edges where weights differ; use Dijkstra's or A* algorithms instead. Also, BFS is inefficient for very large dense graphs without pruning or heuristics.

Production Patterns

In real systems, BFS is used for shortest path in social networks, peer-to-peer networks, and unweighted routing. Bidirectional BFS is common in map services for faster queries. BFS also underpins algorithms for connectivity and clustering.

Connections

Dijkstra's Algorithm

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

Understanding BFS helps grasp Dijkstra's method since it generalizes BFS to weighted cases.

Queue Data Structure

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

Knowing how queues work clarifies why BFS explores nodes level by level.

Wave Propagation in Physics

BFS mimics wavefront expansion where waves spread evenly from a source.

Recognizing BFS as a wave helps understand why it finds shortest paths by expanding uniformly.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops.

Wrong approach:

while(queue.length > 0) {
const node = queue.shift()!;
for (const neighbor of graph.get(node) || []) {
queue.push(neighbor);
}
}

Correct approach:

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

Root cause:

Failing to track visited nodes leads to revisiting the same nodes endlessly.

#2 Trying to use BFS for shortest path in weighted graphs without modification.

Wrong approach:

Use BFS directly on weighted graph edges ignoring weights.

Correct approach:

Use Dijkstra's algorithm or A* for weighted graphs to account for edge costs.

Root cause:

Misunderstanding BFS applicability causes incorrect shortest path results.

#3 Not reconstructing the path, only returning distance.

Wrong approach:

Return distance array without parent tracking, losing actual path info.

Correct approach:

Track parents during BFS and backtrack from target to start to build path.

Root cause:

Overlooking path reconstruction limits usefulness of BFS for real applications.

Key Takeaways

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

Tracking parents during BFS allows reconstructing the exact shortest path, not just its length.

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

Stopping BFS early when the target is found improves efficiency in large graphs.

Understanding BFS's queue-based mechanism is essential for mastering graph traversal and shortest path problems.