N分离度访谈problm

最近有人问了一个关于采访的有趣问题。N分离度访谈problm

例如， A是B朋友，B是C朋友，C是D朋友，d是E朋友，E是F的朋友。所以我们可以说，A知道F。

显然你不能有效地使用BFS或其他标准遍历技术来解决这个问题。问题是 - 如何将数据结构存储在数据库中以及如何快速执行此搜索。

我没有找出答案，也许有人有一个想法？

2017-09-02 silent-box

我*猜*'是'的概率约为99.99999％，所以也许你可以硬编码'返回是'，但我会等待看到答案。 – alain

[挑战，如何实现六度分离算法？]的可能重复（https://stackoverflow.com/questions/2076715/challenge-how-to-implement-an-algorithm-for-six-degree-分离） – sascha

@RoryDaulton不，对不起。修正了 –

BFS有什么问题？

从第一个节点执行BFS的三个步骤，通过标记1标记可访问的用户。它需要10^9个步骤。

从第二个节点执行BFS的三个步骤，通过标记2标记可访问的用户。如果我们符合标记1 - 宾果。

2017-09-02 17:42:13 MBo

如果您不再扩展已标记的节点（用户数为10^6），则需要少于10^6个步骤。 –

@RalfKleberhoff，顶点数达到'pow（10,6）'，但边数达到'pow（10,9）'。 –

如何将数据存储为100万x100万个矩阵A其中A [i] [j]是从用户i到达用户j的最小步数。然后你可以几乎立即查询它。但更新更昂贵。

2017-09-02 19:26:34 algrid

回答