查找两个推特用户关系的算法

Question

我有 6 度的 Kevin Bacon 类型问题。假设我有 2 个推特用户，我想通过 friend (我用 friend 来表示你关注某人与他们关注你的时间)和推特上的关注者来弄清楚他们之间的关系。我的数据库中有所有 ID。

例如:

乔尔和莎莉

Joel 跟随 Fred，Fred 是 Steve 的 friend ，Steve 跟随 Sally。

可能有多种方法可以到达那里，但我想要最短的。

这似乎是一个众所周知的计算机科学问题(最短路径算法)。

今天我有一个名为“影响者”的表，其中存储了我所有的推特 ID，然后我有一个关注表，它是一个 self 引用表(一侧是关注者的 ID，另一侧是 friend 的 ID。)

那么这是图论吗？如果可以，有人可以指出任何有用的实用程序/库/方法。我使用的是 ruby​​，但可以解析大多数语言。

Answer 1

如您所说，这是一个众所周知的问题，您可以在 Wikipedia 中看到.

请注意，在您的情况下，所有边的权重都等于 1)，因此我认为 Djikstra 的算法对您不是很有用。

为了找到最小距离，我建议使用广度优先搜索。问题是 Twitter 网络可能是极度连接的，因此你可能会出现组合爆炸(假设每个人都与其他 20 个人连接——在第一层，你会访问 20 个个人资料，而在下一个你会访问 400 个) ，然后在接下来的 8000 年内——如果你不能快速找到 Sally，你很快就会耗尽内存)。

还有一个线性规划公式，我不是 100% 熟悉。 These notes擅长线性规划，但不擅长最短路径问题，而 these似乎更专注于应用程序。

有一个video lecture关于这个问题的在线资料似乎很完整。

我希望这些引用资料有所帮助。