- DFS’s discovered nodes are processed in last-in-first-out order
- BFS’s discovered nodes are processed in first-in-first-out order
Here’s a demonstration (traversing a tree, for simplicity):
… notice the commonalities between
breadthFirstSearch. Extracting this commonality to a poorly named function
search might make it clearer:
Interesting? Well, it interested me. What other algorithms become easier to write when you have a “call queue”? Can this idea be generalised?
Update: Perry Lorier suggests a generalisation might be continuation style passing.
Update: Corecursion looks related