7

这是我最近在网上找到的一个面试问题：

您如何找到 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。在面试中这是可以接受的答案吗？我在上述推论中有任何错误吗？还是我错过了任何更好的解决方案？

提前致谢。

4

2 回答 2

10

更好的解决方案可能是同时从两个节点启动 BFS。类似于以下伪代码：

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)，这在大图中可以快得多。

于 2013-03-10T01:17:39.593 回答
1

如果您正在寻找两个特定人之间的分离程度，我会使用Dijkstra 算法，它会找到从选定源到所有可到达节点的最短路径。

于 2013-03-09T22:38:21.043 回答