Concept
BFS explores a graph level by level from a start node using a queue, visiting every node at distance d before any at d+1. In an unweighted graph the first time it reaches a node is along a shortest path.
The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.
A few lines that show Breadth-first search doing its job.
from collections import deque
def shortest_path_length(graph, start, goal):
queue = deque([(start, 0)])
seen = {start}
while queue:
node, dist = queue.popleft()
if node == goal:
return dist
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt) # mark when enqueued
queue.append((nxt, dist + 1))
return -1Marking a node visited when it is dequeued rather than when it is enqueued. The same node is queued many times, the work balloons, and on a grid the queue can grow to the square of what it should be.
Your roadmap puts these before Breadth-first search, unless you already know them.
Once a session shows you understand Breadth-first search, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.
Topics that build on Breadth-first search.