BFS and DFS in Problem Solving

13 Nov 2018

I think a lot of problem solving can be summarized into two steps.

  1. Generate possible approaches to solve said problem.
  2. Go drill down on that approach and go as far as you can with that approach. Pray to God you didn’t make an assumption that will kill your approach and lead you to a dead end.

In computer science, the two of the most fundamental graph searching algorithms are breadth first search and depth first search. I think #1 ties into breadth first search, and #2 ties into depth first search.

I’ve come up with a good example of how both works!

Let’s say that you want to get a phone number of a student at your school. Let’s call him Greg.

Now the constraint is that you don’t have a phone book(which is effectively an index). No Google, no internet. NOTHING. Pretend this was in the 70s. How would you get this guy’s number?

Breadth First Search Approach:

One approach is ask all of your friends. You ask your close friends Sarah, Matt, and Caleb.

They say no, but they give you a list of their friends who could have Greg’s number.

So you put those people’s names, and you go hunt them down. Let’s call them Abby, Bacon, Chris, Duncan, and Erfan.

But they don’t have Greg’s number either, so they all give you their friends contact. You poll them into a huge list.

Now you use that list to ask those people. You do this over and over until you find Greg’s number. Or the man himself =D.

Depth first Search Approach

Instead of asking your friends one by one, you pick one friend you like the most. Matt.

You ask Matt. Matt doesn’t have Greg’s number. But Matt points you to David.

You ask David. David doesn’t have Greg’s number, but he thinks Peter has Greg’s number.

You ask Peter, who refers you to Nathan, and Nathan refers you do whoever else, and you do this until you find the person who has Greg’s number.

I would like to say that both approaches to get Greg’s number are valid, but there are definitely tradeoffs of picking either breath first search or depth first.

Problem Solving and Graph Algorithms

First, you have to generate all possible approaches. You go through all of them, evaluate their potential. Now these ideas can lead to other sub-ideas, so you explore them at a very shallow level. But you don’t want to chase the rabbit too hard - you want to see things at surface level.

Afterwards, you pick an idea that you predict to be effective. You drill down on that idea hard, and go for it.

Effectively, you’re using bfs and dfs for problem solving. Of course, depending on your results of dfs, you could climb back up and swap to bfs instead. So the analogy here isn’t 1:1.