Effective way to find degrees of separation between two nodes in a graph

Question

This is a question from an interview I recently found on the Internet:

How would you find the degree of separation between two people on Facebook? Discuss various ideas, algorithms, and trade-offs. (Determining the degree of saparation: http://en.wikipedia.org/wiki/Six_degrees_of_separation )

Here is what I think of it:

The candidate algorithms that I can come up with include: Width search (BFS), Depth search (DFS), Depth search (DLS), Iterated deep search (IDS).

First, DFS should be considered. It is very likely that even when both people are connected (i.e. degree of separation = 1), the algorithm can continue to search the wrong path for a long time.

BFS is guaranteed to find a minimum degree of separation (since the graph is not weighted). Assume that the maximum branching coefficient is b, and the actual degree of separation between the two target people is d, and the time complexity and space complexity will be O (b ^ d).

Since the maximum possible degree of separation is unknown (although it should not be higher than 6), it is not recommended to use DLS. Nevertheless, IDS seems to be a better idea than BFS - the time complexity is also O (b ^ d) (although the actual time is slightly higher than BFS due to repeated visits to intermediate nodes), while its spatial complexity is O (bd), which much better than O (b ^ d).

In the end, I would choose IDS. Is this an acceptable answer in an interview? Am I really mistaken in the above conclusion? Or are there any better solutions that I missed?

Thanks in advance.

Answer 1

A better solution would be to run BFS from both nodes simultaneously. Something like the following pseudocode:

nodes1 = (A); nodes2 = (B); d = 1; loop { nodes1 = neighbors(nodes1); if (intersects(nodes1, nodes2)) { return d; } d += 1; nodes2 = neighbors(nodes2); if (intersects(nodes2, nodes1)) { return d; } d += 1; } 

The time complexity of this algorithm is about O(m ^ (d/2)) , where m is the maximum degree of all nodes and d is the maximum distance. Compared to a simple BFS with O(m ^ d) , this can be much faster on large graphs.

Answer 2

If you are looking for a degree of separation between two specific people, I would use the Dijkstra algorithm , which will find the shortest paths from the selected source to all available nodes.