Tom's Blog

Breadth-first search with setTimeout(f, 0)

The two most popular graph traversal algorithms are depth-first search (DFS) and breadth-first search (BFS). Their difference is that:

  • DFS’s discovered nodes are processed in last-in-first-out order
  • BFS’s discovered nodes are processed in first-in-first-out order

Consequently, DFS is easily implementable as a recursive function, where the call stack acts as the stack. The implementation for BFS is less simple, however, because we must keep track of an explicit queue. Or must we… what if our language provided a “call queue”, or some such. Javascript does such a thing: the JS event loop.

Here’s a demonstration (traversing a tree, for simplicity):

See the Pen Computing with Queues: #1 by Tom (@tomfitzhenry) on CodePen

… notice the commonalities between depthFirstSearch and breadthFirstSearch. Extracting this commonality to a poorly named function search might make it clearer:

See the Pen Computing with Queues: #2 by Tom (@tomfitzhenry) on CodePen

Don’t use this code. As well as it not being clear or idiomatic, users of a BFS function would expect the BFS to be completed before the JS event queue is polled again, which this BFS implementation breaks

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

blog comments powered by Disqus