Coding Interview: Patterns & DSA · Trees & Graphs · Lesson 2 of 3
Graphs: BFS & DFS
A graph is nodes connected by edges; a tree is just a graph with no cycles and one path between nodes. The two fundamental traversals are BFS (breadth-first, a queue) and DFS (depth-first, a stack or recursion). Both are O(V + E) — vertices plus edges.
- BFS: explore level by level with a queue. On an unweighted graph it finds the shortest path (fewest edges).
- DFS: go as deep as possible before backtracking, using a stack or recursion. Natural for connectivity, cycle detection, and path existence.
- Always track visited: without a visited set, cycles make either traversal loop forever.
from collections import deque def bfs_shortest(graph, start, goal): q = deque([(start, 0)]) visited = {start} while q: node, dist = q.popleft() if node == goal: return dist for nb in graph[node]: if nb not in visited: visited.add(nb) q.append((nb, dist + 1)) return -1
BFS for shortest, DFS for existenceOn an unweighted graph, BFS gives the shortest path because it reaches nodes in order of distance. DFS does not — it finds a path, not the shortest. For weighted graphs you need Dijkstra (non-negative weights) instead.
Grids are graphsMany 'matrix' problems (number of islands, flood fill, rotting oranges) are graph traversals in disguise: each cell is a node, adjacent cells are edges. Recognize the grid-as-graph and BFS/DFS solves it.
◆ Lock it in
- BFS (queue) finds the shortest path on unweighted graphs; DFS (stack) finds existence/connectivity.
- Both are
O(V + E); always keep a visited set to avoid infinite loops. - Grid problems are graphs — cells are nodes, neighbors are edges.
Feynman drill — say it out loudExplain why BFS finds the shortest unweighted path but DFS generally does not.
Step 1 rate your confidence · Step 2 pick your answer
To find the shortest path (fewest edges) in an unweighted graph, use:
Step 1 — how sure are you?