The first, and one of the most common methods to search is using a breadth first search (BFS) pattern. In this case, you start at the root node of the tree, and evaluate the first child determining if you have a match. If not, you move to its sibling and then the next, until there are no more children nodes of the root node to search.
If you do not find a match in the root nodes children, then you go to the first child, and search it’s children. Then the second child, and search it’s children, etc. If you visualize your tree, you can see you stay on the same node “level” and search all of the children at that level until the node you are looking for is found.
Consider the game of Six Degrees of Separation for a moment. In it, we’re told that every person is related to any other person through six degrees of separation or less. For example, my neighbor, went to school with a someone, who worked with someone who attended a wedding that your cousin also attended. Thus we could find our separation as me > neighbor > school buddy > co-worker > wedding attendee > cousin > you.
There is a famous game with the same idea called Six Degrees of Kevin Bacon. (https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon)
In Six Degrees of Kevin Bacon this is slightly narrowed by saying almost everyone in Hollywood has worked within six degrees of Kevin Bacon. If you put Kevin Bacon at the root node, then the children nodes could be all the actors from movies he’s worked on.That would be the first layer of people associated with Kevin Bacon.
We could then search that list and see if we can find the person we’re trying to match with Kevin Bacon. If we cannot find a match, then we build the next layer. Each of those people have movies associated with them, and people associated with those nodes. We assign the new people as children to the person that they are associated with based upon the movie that they worked together.
If you were to then determine everyone who worked on a movie with any of that second level, you’d have your third layer, and so on and so on out to presumably layers.
To simplify the process, you should remove anyone who you’ve already identified in a previous layer so you don’t have redundancies. It is common for people to work with the same people over and over, and you want to avoid checking the same people two, three, or even more times.
As you can see, this logic is a little busy, but it allows us to build a hierarchical tree and we can quickly find the closest path from an actor to Kevin Bacon. Because we search across the same level at each time, we find a closer link than if we were to search using other means.
This methodology allows us to find the fastest match, which is a key computer science concept and is known as a shortest path algorithm.
Interesting Note: Kevin Bacon was thought to be the “Center of the Hollywood Universe”. Turns out, he isn’t the best person. In fact, he’s not even in the top 100. But he is better than 99% of all other actors out there, and you can find almost anyone connected to Mr. Bacon within six degrees of separation. When a website to test this theory first came out, some co-workers and I tried obscure people, older actors, etc, and almost always got a match.
Breadth First Searching was originally found on Access 2 Learn
