Graph Search
BFS
Now let’s say that you really hated the name Carmen, because that is something that you would do. That’s what people think of you. And you are the type of person to take this next level. Not only do you not want friends named Carmen, but you don’t want to be friends with anyone who knows anyone named Carmen. There are two ways to handle that situation.
First, you could go through all of your friends, asking their names, and if anyone is named Carmen, you cut them out (don’t kill them, as this is highly illegal and your defense would be flimsy at best). Next, you go through your friend's friends, cutting out friends who have friends named Carmen. But your craziness doesn’t stop there, you have to check your friend's friend's friends, since if they know a Carmen, then through the transitive property your friend knows a Carmen, and then you know a Carmen. Dear GOD!
That is called Breadth First Search. I will show you an example, but it is going to take the most imagination of all. We have to pretend you have friends.
You—> Bill, Lolita, Jimmy
They are all clean so you go through their friends.
You —> Bill, Lolita, Jimmy —> Bill’s friends(Caleb, Sophie, Ben)…etc.
You add each person’s friends after searching them. By contrast you
could search each friend individually, then their friends, then their
friend's friends.
You —> Bill —> Caleb —> no friends
You —> Bill —> Sophie —> Jimmy —>… Too many to imagine
You—> Bill —> Ben —> Dr. Urchin —>…who cares, you get it.
DFS
In Depth First Search, instead of searching your friends, then your friends friends, then your friends friends friends, etc. you search each friend’s connections first. Rooting out the Carmen’s one friend at a time. The better depends on which way will lead to a Carmen the fastest.
A more straightforward example would be if you live in the city and you are looking for a peach farmer. Are you going to search your friends, and then their friends? No way! A peach farmer is more likely to be a friend of a friend’s friend. So you should pick the person who is most likely to have a peach farmer in their network. Like Jimmy, he knows everyone. That would be Depth First Search.
But if you are a farmer and you are looking for a peach farmer, your direct friends are more likely to have those connections, so you might use Breadth First Search instead, but that depends on the farmer.
The Big O notation is tricky for this one. So we have to make sure we are not visiting nodes twice, since in that case this could take an infinite time period.
Big O would be O(N) where N is the number of nodes.
Comparing BFS and DFS
If you think about this, one of those searches is actually slightly more optimal than the other. Did you figure it out? I am sure you did. In an unbalanced tree, there is little difference, but there is an interesting edge case to think about. Let's assume a balanced tree. That means the depth of the tree is lg n, and the tree has similar or equal left and right sub-trees. If you do DFS, at most you will go lg n elements deep, storing lg n in recursive stack calls. In BFS, you will not do that, in the worst case you will store half of all of the nodes on a graph.
Think of the way BFS works. You search all children of a node, then you search each of the children's children. So, imagine yourself on the second to last level of a tree. At this point, you will add each of their children. If the tree is balanced, than as you go farther down, the more children each node has. Meaning data is concentrated towards the bottom, and on the final level, you have half of all the data in the tree. So, when you BFS the final level of a tree, you are storing half of the entire tree in memory. Ouch.