Graph traversals·5 min
BFS, DFS, and the frontier
0 / 1
Two ways to walk a graph. BFS explores in rings of increasing distance (a queue). DFS plunges down one path then backtracks (a stack, or recursion). Both reduce to the primitive you just built: neighbors().
BFS gives you shortest hop-distance for free — the first time you reach a node, it's via a shortest path — which is why the shortest-path step builds on BFS. And the visited set is non-negotiable: graphs have cycles (this one has a 3-edge FOLLOWS cycle among reviewers). Without visited you loop forever.
BFS rings from Kevin Bacon over ACTED_IN (BOTH)
ring 0: {Kevin Bacon}
ring 1: movies he acted in (follow ACTED_IN, OUT)
ring 2: co-stars of those movies (follow ACTED_IN, IN) <- Bacon number 1