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

Question

This is an interview question that I recently found on Internet:

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

Here's what I think about it:

The candidate algorithms that I can think of are: breadth-first search(BFS), depth-first search(DFS), depth-limited search(DLS), iterative-deepening search(IDS).

First, DFS should be taken of consideration. It is very likely that even when the two persons are connected (i.e. degree of separation = 1), the algorithm may keep searching along a wrong path for a long time.

BFS is guaranteed to find the minimum degree of separation (since the graph is not weighted). Assume the max branching factor is b and the actual degree of separation between two target persons is d, both time complexity and space complexity would be O(b^d).

Since the max possible degree of separation is unknown (although it should not be too higher than 6), it may not be a good idea to use DLS. However, IDS seems to be a better idea than BFS - it's time complexity is also O(b^d) (although the actual time cost a bit higher than BFS due to repeated visiting of intermediate nodes), while its space complexity is O(bd), which is a lot better than O(b^d).

After all, I would choose IDS. Is that an acceptable answer in an interview? Did I mid any mistake in the above inference? Or are there any better solutions that I missed?

Thanks in advance.

Answer 1

A better solution might be to start a BFS from both nodes simultaneously. Something like the following pseudo-code:

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 a lot faster in large graphs.