Breadth-First Search
Medium+80 XPExplore a graph level by level using a queue — nearest nodes first.
No visualization loaded.
Watch
—
Press Run to begin.
A graph is dots (nodes) joined by lines (edges) — think cities linked by roads, or people linked by friendships. Breadth-First Search explores it in rings: visit the start, then everything one step away, then everything two steps away, and so on. It uses a queue (first-in-first-out) to remember who to visit next, so it always spreads out evenly — which is why it finds the SHORTEST path in steps.
▸What are nodes, edges, and 'neighbours'?
A node is a dot (a city, a person, a web page). An edge is a line connecting two nodes (a road, a friendship, a link). Two nodes joined by an edge are 'neighbours.' A graph is just a pile of nodes and the edges between them — more free-form than a tree, since edges can go anywhere, even in loops.
▸Why a QUEUE, and why does that give level-by-level order?
A queue serves oldest-first (FIFO, from the stack/queue lesson). You add the start, then add its neighbours to the back. Because you always take from the front, you finish all the 1-step nodes before any 2-step node gets its turn. That front-to-back discipline is exactly what produces neat expanding rings.
▸What's the 'visited' set for?
Graphs can have loops, so without bookkeeping you'd revisit nodes forever. You mark each node 'visited' the first time you reach it and skip it if you meet it again. That guarantees every node is handled once — and is why BFS runs in O(nodes + edges).
▸When would I use BFS?
When you want the fewest-steps path: shortest route in an unweighted maze, fewest intros to connect two people, fewest clicks between pages. BFS reaches nearer nodes first, so the first time it touches your target, it's via the shortest path. Need to go deep instead of wide? That's DFS, coming next.
How the work grows
O(nodes + edges) is fair — grows in step with the data. Each node is visited once and each edge looked at once, so time grows in a straight line with the size of the graph. Space holds the queue of nodes to visit plus the visited set.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.