BFS / DFS

BFS (Breadth-First Search)

Start at a node, visit all its neighbors, then all THEIR neighbors, etc. Uses a queue. Guarantees shortest path in unweighted graphs because it explores nodes in order of their distance from the source.

O(V + E)

O(V)

How It Works

Breadth-first search explores a graph level by level. Starting from a source node, it visits all neighbors at distance 1, then distance 2, and so on, using a FIFO queue to hold the frontier. Each node is marked visited when it is enqueued, so no node enters the queue twice. Because nodes are dequeued in non-decreasing order of distance, the first time BFS reaches a node it has found a shortest path to it in an unweighted graph.

The running time is O(V + E): each vertex is enqueued once and each edge is examined at most twice (once from each endpoint in an undirected graph). Compared to trying every possible path — which is exponential — BFS settles each node exactly once, which is what makes shortest-path queries on unweighted graphs cheap.

Step-by-Step Visualization

BFS from node 0. Graph: 0→[1,2], 1→[3], 2→[4]

Queue[0]

Visited{0}

1/4

Code

Java

static void bfs(List<List<Integer>> graph, int start) {
  Set<Integer> visited = new HashSet<>();
  visited.add(start);
  Queue<Integer> queue = new LinkedList<>();
  queue.add(start);

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

Tips & Gotchas

1Use a queue. Visit all neighbors before going deeper

2Mark nodes as visited BEFORE adding to queue (not after popping)

3BFS finds shortest path in unweighted graphs

Practice Problems

1Word Ladder
2Shortest Path in Binary Matrix
3Open the Lock
4Nearest Exit from Entrance in Maze

About the BFS / DFS Pattern

The two fundamental ways to explore a graph. DFS goes as deep as possible before backtracking (uses a stack or recursion). BFS explores all neighbors first before going deeper (uses a queue). Both visit every node exactly once.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

When should I pick BFS over DFS?

Use BFS whenever the answer involves shortest distance or fewest steps in an unweighted graph, because BFS visits nodes in order of distance from the source. DFS gives no distance guarantee and can wander down a long path first. For pure reachability or connectivity, either traversal works.

Why must nodes be marked visited when enqueued rather than when dequeued?

If you mark on dequeue, the same node can be enqueued many times by different neighbors before it is processed, blowing up the queue and potentially degrading the runtime. Marking on enqueue guarantees each node enters the queue exactly once and preserves the O(V + E) bound.

How do I recover the actual shortest path, not just its length?

Store a parent pointer for each node when you first enqueue it. After BFS reaches the target, walk parent pointers back to the source and reverse the sequence. This adds only O(V) extra space.