Graph BFS / DFS
Traverse graphs using BFS (shortest path, level-by-level) or DFS (connected components, path existence). Always track visited nodes to avoid cycles.
Time
O(V + E)
Space
O(V)
Recognize it when
- Count connected components / islands
- Shortest path in unweighted graph (BFS)
- Flood fill, bipartite check
- Multi-source BFS (rotting oranges)
Questions — ordered by difficulty
Number of Islands
Count the number of islands (connected groups of '1') in a 2D grid.
Clone Graph
Return a deep copy of a connected undirected graph.
Pacific Atlantic Water Flow
Find all cells from which water can flow to both the Pacific and Atlantic oceans.
Rotting Oranges
Find how many minutes until all oranges are rotten. Rotten oranges infect adjacent fresh oranges each minute.
Walls and Gates
Fill each empty room with the distance to its nearest gate.
Word Ladder
Transform beginWord into endWord by changing one letter at a time, using only words from wordList. Find the shortest transformation sequence length.
Redundant Connection
In a tree with n nodes and n edges (one extra edge creates a cycle), find the redundant edge that can be removed to restore the tree.
Accounts Merge
Merge accounts that share any email. Each account has a name and list of emails. Accounts belong to the same person if they share any email.
Critical Connections in a Network
Find all critical connections (bridges) in a network — edges whose removal disconnects the graph.
Reconstruct Itinerary
Given a list of airline tickets [from, to], reconstruct the itinerary starting from "JFK". Use all tickets exactly once. If multiple valid itineraries exist, return the lexicographically smallest one.
Swim in Rising Water
Find the minimum time to swim from top-left to bottom-right of a grid, where you can only move to cells with value ≤ current time.
Number of Connected Components in Undirected Graph
Given n nodes and a list of edges forming an undirected graph, return the number of connected components.
Surrounded Regions
Capture all regions of 'O' surrounded by 'X'. A region is captured by flipping all 'O's into 'X's.