Module 4 · Graphs, greedy and interview polish Lesson 12 of 15
Graphs: BFS and DFS
A graph is nodes and edges; BFS explores level by level and finds the shortest number of steps, while DFS goes deep and is the base for many recursive answers.
The concept
Keep a visited set from the start, or a graph with a cycle loops forever - the single most common bug in a first BFS.
Grid problems are graphs in disguise: each cell is a node and its four neighbours are edges. Seeing that turns a scary question into BFS you already know.
from collections import deque
def shortest(graph, start, goal):
q = deque([(start, 0)])
seen = {start}
while q:
node, dist = q.popleft()
if node == goal:
return dist
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, dist + 1))
return -1Worked example
Shortest path in a grid, or "fewest changes to reach a state", is BFS with a queue; "does a path exist" or "count the islands" can be DFS.
Your practice task
Write BFS that returns the shortest distance between two nodes in an unweighted graph.
Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.
Key takeaway
Keep a visited set from the start, or a graph with a cycle loops forever - the single most common bug in a first BFS.
Keep your place in this course
A free account saves which lessons you have finished and unlocks the certificate. The lesson itself stays free to read.
Create free account or sign inCourse complete
You finished every lesson.
Your certificate is ready, and the projects you built are the proof to attach to an application.
Almost there
15 lessons left of 15
Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.