From purely my knowledge of computer science a simple breadth first search from

Question

From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A and B have 6 degrees of separation. If I simply wanted to check whether B is within 6 degrees I could also limit my depth to 6.

I have heard however that there are better ways of doing this using bidirectional methods which involve some heuristics. I was wondering if someone could explain the most effective way of doing this and compare space and time complexity between the different approaches. Thanks!

And as a followup, what would be a good algorithm for finding the degree of separation between two arbitrary nodes A and B and the path between them?

Explanation / Answer

You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether each element belongs to the first list.

To determine whether the lists intersect, you have two options: either sort the first list, or put it into a hash table. The second uses more space but it's faster. (You will need counterparts of these, a balanced binary tree or a hash table, to generate the lists in the first place.)

Practically speaking, you would apply the following optimization: first determine all nodes at distance 1 from A and all nodes at distance 1 from B, and check whether the lists intersect. Then check all nodes at distance 2 from A against all nodes at distance 1 from B. Then check all nodes at distance 2 from A against all nodes at distance 2 from B. And so on. If the distance is less than 6, then you potentially save a lot of time and space.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.