Shortest Path in Unweighted Graph

Why does BFS guarantee the shortest path in unweighted graphs?

Word Ladder (BFS Shortest Path)

Find the length of shortest transformation sequence from startWord to endWord.

Pacific Atlantic Water Flow (DFS Traversal)

Find grid coordinates where water can flow to both Pacific and Atlantic oceans.

Graph Algorithms & TraversalsAdvanced LevelStudy Time: 30 mins

BFS & DFS Algorithm

Breadth-First Search (BFS) explores graph nodes level-by-level using a Queue. Depth-First Search (DFS) explores as deep as possible along each branch using a Stack or Recursion.

BFS & DFS Graph Traversal Visualizer

Traverse tree network using BFS (Queue) or DFS (Stack) traversal rules.

Active Queue (FIFO)

Empty

Visited Order Log

None

Speed:

Real-world analogy: Ripples vs Shaft Explorer

BFS

DFS

Hover over items for details

BFS is like ripples expanding outward in water (level by level). DFS is like a cave explorer walking down a tunnel to the bottom before backtracking.

BFS= Uses Queue (FIFO) for shortest path in unweighted graphs.
DFS= Uses Stack / Recursion (LIFO) for pathfinding and cycle detection.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapBFS & DFS: O((V + E) log V) Time

Hover curves to inspect classes

Time Steps (N=500)

~4,483 steps (Linearithmic)

O((V + E) log V) Time

Space Footprint

O(V + E) Graph Memory

Memory growth rate as N expands.

Performance Rank

Moderate Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
BFS Time & Space	O(V + E)	O(V)
DFS Time & Space	O(V + E)	O(V)

Code implementations

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