Breadth-first and depth-first search
Compare two fundamental ways to explore a graph: spreading out layer by layer or following one path deeply before backtracking.
Big idea
How it thinks about the graph
BFS uses a queue and is naturally good at finding shortest paths in unweighted graphs. DFS behaves like a stack or recursion path and is good for exploring structure.
Useful when
Reachability, connected components, maze exploration, tree traversal and unweighted shortest paths.
Watch out: Traversal order depends on the order neighbours are checked. The same graph can produce different valid orders.
Questions to investigate
Which vertices are discovered first?
When do BFS and DFS give the same order?
Can you build a graph where their behaviour is clearly different?
Open the interactive explorer
This algorithm already has a working prototype. Use it to build a graph, make a prediction, then step through the search.
Open Breadth-first and depth-first search explorer