Depth First Search… or Searching for Atlantis.

This is going to be a short one. Because the analogy here is much more intuitive and can more easily be applied to a range of circumstances…

Imagine you’re on a yacht near the Bimini Islands searching for The Lost City of Atlantis. You have “reliable” info that the city may be somewhere in the vicinity, but aren’t sure where. Also, “somewhere in the vicinity” happens to be two square miles so it could take forever. You’ve got an optic cable that you can drop into the murky depths, but you’ve got limited battery power so you can’t just leave the camera on and drive around.

You have reasonable expectation that the bottom of the ocean is mostly level, although you know there are trenches and canyons. You’ve also have an expectation that some ancient towers of The Lost City of Atlantis might be sticking up from the bottom of the sea. So, what’s the best way to search for Atlantis?

Depth First Search, of course!

If you were doing a breadth first search, you’d waste a lot of time searching the intermediary heights/depths of the ocean with zero expectation of finding what you’re looking for.

With a depth first search, you’ll drop your cam-line until it hits bottom, whatever/wherever bottom is.

((and that’s it.))

To extend/mix up the analogy: if you were on a beach and knew some pirate treasure was buried in the local vicinity, you’d dig down to the expected depth before starting a new hole.