Explore graphs with BFS and DFS
Model problems as graphs and search them without revisiting nodes.
- Represent a graph with an adjacency list or grid.
- Choose between breadth-first and depth-first search.
- Count connected components and find shortest paths.
Many interview problems are graphs in disguise: grids of land and water, course prerequisites, word ladders, social networks. A graph is nodes plus edges; in code it is usually an adjacency list (a dict from node to neighbors) or an implicit grid, where each cell’s neighbors are up, down, left, and right. The two fundamental searches visit every reachable node once, in O(V + E) time.
BFS versus DFS
- Breadth-first search (BFS) uses a queue and explores in rings of increasing distance. It finds the shortest path in an unweighted graph.
- Depth-first search (DFS) uses recursion or a stack and follows one path as far as possible. It is natural for connected components, cycle detection, and topological sort.
- Both need a visited set (or marking cells in place) so nodes are not processed twice - otherwise cycles cause infinite loops.
1from collections import deque
2
3graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["E"], "E": []}
4
5def shortest_steps(start, goal):
6 queue = deque([(start, 0)])
7 visited = {start}
8 while queue:
9 node, steps = queue.popleft()
10 if node == goal:
11 return steps
12 for neighbor in graph[node]:
13 if neighbor not in visited:
14 visited.add(neighbor)
15 queue.append((neighbor, steps + 1))
16 return -1
17
18print(shortest_steps("A", "E"))3
To count connected components - such as islands in a grid - loop over every node; whenever you find an unvisited one, increment the count and flood-fill everything reachable from it with BFS or DFS. Each cell is visited once, so the whole scan is O(rows × cols).
Key takeaways
Adjacency lists and grids are the common graph representations.
BFS for shortest unweighted paths; DFS for components, cycles, and ordering.
Always track visited nodes; both searches are O(V + E).
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Count islands
Read the number of rows, then that many rows of 1 (land) and 0 (water). Print the number of islands: groups of land cells connected up, down, left, or right.
- Three islands
- One island
- No land
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…