BeginnerCoder
DonateLesson 18 — BFS traversal
BFS: explore level by level
Breadth-first search (BFS) explores a graph in waves: first the start, then all its neighbours, then their neighbours, and so on. It uses a queue, plus a seen set so no node is visited twice. Recording the distance (number of hops) when a node is first seen gives the shortest path in an unweighted graph.
hops = {"home": 0}
# neighbour nb of cur, first time seen:
hops[nb] = hops[cur] + 1
Why it matters: "degrees of separation" in social networks, web crawlers and maze solvers are BFS.
For each neighbour not yet in dist, record it as one hop further than u and add it to the queue.
Run your code — when the output matches the task, you will see a green check. Then mark the lesson complete.
Test your knowledgeA quick 3-question quiz on this lesson — instant feedback.
Ready for more? Optional paid resources that pick up where this lesson leaves off.
Some links on this page are affiliate links: we may earn a commission at no extra cost to you. As an Amazon Associate I earn from qualifying purchases.
Project-based Data Structures courses if you want a structured paid path after the free lessons. Wait for a sale — prices drop often.
Browse on Udemy →Search Amazon for Data Structures books — check the publication year so the examples match current versions.
Search Amazon →