在图中高效地找到两个节点之间的距离的方法

Question

这是我最近在互联网上发现的一道面试题：

如何在Facebook上找到两个人之间的分离度？讨论不同的想法、算法和权衡。(分离度的定义：http://en.wikipedia.org/wiki/Six_degrees_of_separation)

以下是我的想法：

我能想到的候选算法有：广度优先搜索(BFS)、深度优先搜索(DFS)、深度限制搜索(DLS)、迭代加深搜索(IDS)。

首先，应该考虑使用DFS。即使两个人已经连接（即分离度=1），该算法也很可能会沿着错误的路径搜索很长时间。

BFS保证可以找到最小分离度（因为图没有权重）。假设最大分支因子为b，两个目标人物之间的实际分离度为d，则时间复杂度和空间复杂度均为O(b^d)。

由于最大可能的分离度是未知的（虽然不应该太高于6），使用DLS可能不是一个好主意。然而，IDS似乎比BFS更好 - 它的时间复杂度也是O(b^d)（尽管由于中间节点的重复访问实际时间成本略高于BFS），而其空间复杂度是O(bd)，这比O(b^d)要好得多。

毕竟，我会选择IDS。这在面试中是可以接受的答案吗？我在上述推论中犯了任何错误吗？还是有任何更好的解决方案我错过了吗？

提前感谢。

- quantumrose

Answer 1

一种更好的解决方案可能是同时从两个节点开始执行广度优先搜索。伪代码如下：

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;
}

此算法的时间复杂度大约为O(m ^ (d/2))，其中m是所有节点的最大度数，d是最大距离。与简单的BFS O(m ^ d)相比，在大型图中这种方法可以更快。

- nwellnhof

---

我以前没有考虑过双向搜索。谢谢你提到它。 - quantumrose

Answer 2

如果您想要计算两个特定人之间的联系程度，我建议使用Dijkstra算法，该算法可以找到从选定源节点到所有可达节点的最短路径。

- phs

---

如果边没有权重，Dijkstra算法和BFS有什么区别？ - angelatlarge

可能没有什么特别的含义。但是，面试官问这个问题很可能是想看看候选人是否具备基本的图算法知识，即是否能够熟练掌握“Dijkstra”和“Prim”。 - phs

@angelatlarge 如果使用A*算法，如何找到一个合适的启发式函数？ - quantumrose

我看不出A*算法能有什么帮助。没有办法估计到目标节点的距离。 - Eyal Schneider

公平的问题。在Facebook中，我会考虑一些教育机构、工作地点、兴趣爱好、地理位置和家庭关系的组合。如果通过具有共同兴趣爱好的人来寻找联系，似乎更容易找到较少的分隔度。具体来说，如果我从A开始，试图找到与B之间的最小距离，我应该先搜索与B更多共同点的人。不过现在我想了想，这是不正确的：为确保你有最短的距离，你必须搜索所有内容。 - angelatlarge