Your cart is currently empty!
Breadth First Search… or Unclogging The Bathtub
Encouraged by Flatiron instructor Jonathan Foster to make a blog post out of a Slack comment where I attempted to explain “Breadth First Search” in plain English, I thought it was time to finally kick off this blog about Better Heuristics for Understanding Code.
If you don’t know what breadth first search is, you will soon.
SO, imagine you’ve got a clogged bathtub, and behind the wall there are three separate pipes you can’t see, any one which could be the cause of the clog. The problem is, each of those three pipes has another two to four pipes branching off, and so on, down each level…
Imagine a maze of pipes descending into the depths of a Dante-esque/Hieronymous Bosch sewer system, a Hell of pipes for you to get lost in. If you were to snake every line in a “depth first” (as opposed to “breadth first”) manner, you might get stuck snaking hundreds of feet of piping when the clog was only two feet away, but on the last top level line.
I know what you might be thinking: “but what if the clog really is in the first line (and hundreds of feet deep)… wouldn’t then breadth first search turn out to be a worse option?” In short, yeah. It would. But you can’t depend on getting lucky. Also, it’s better to snake only the first few feet of bilge-slime that’s come out of your own apartment, than to dredge something up from the public sewer.
One final thing that’s implicit with this analogy that you may find helpful: a breadth first search is the way to go when you have an expectation that you don’t need to go many levels down. (As with bathroom clogs, chances are: the clog isn’t that far away).
Back to the analogy, in your mind’s eye, picture what’s behind the wall: Aside from rats, roaches, and centipedes having a party, the first three pipes immediately behind the wall require you to only extend a snake about two feet deep…
So, as you struggle over the flooded bathtub, you extend about two feet of snake down into the drain. And, in the darkness behind the wall, the head of the snake attempts to find a clog, first to the left, then down the middle, and then finally down the right pipe…
After snaking two feet in each direction on the first level, you then start over and extend the snake maybe 5 feet deep… you jiggle the snake down the few pipes sprouting off the first (left) line and repeat for each offshoot of level one.
Still no clog?
Repeat the process, from left to right, completing each row/level before descending to new depths…
Over and over. Maybe you’re at 20-feet of snake, when the head, several levels down, finally collides with something nasty that’s backed up from your neighbor’s line.
You prod the clog cautiously, daintily, for fear that you might puncture the pipe, cause a flood, and get sued by the landlord for not calling a plumber. The world has no place for pipe-snaking-vigilantes like you.
Fortunately, the pipe DOES NOT puncture and as you ‘squish squish squish,‘ the serrated edge of the snake hooks on to a clump of cat litter… and you’re able to drag it up the pipe.
Your breadth first search is a victory. You’ve unclogged the bathtub, and once you get that cat litter DNA tested, you’ll have the evidence you need to get your horrible neighbor evicted for dumping crystallized cat turds down their toilet on the shared line.