javascript - 如何找到两个抽象节点之间的路径

Question

我想检验“小世界”或“六度分离”假说，即任何人都可以通过 6 个共同 friend 联系到另一个人的理论。 (即 friend 的 friend 的 friend 的 friend 的 friend 的 friend 的 friend 的 friend )

示例节点数据 (JSON):

{
    "name": "John Smith",
    "friends": [
        "Foo Bar",
        "John Doe"
    ]
}

就像这样会有数百个对象，每个对象都相互链接。我想找到它们之间的最短路径。诸如游戏中的寻路算法是否适合这样的抽象概念(即:在 2D 或 3D 世界中无法表示的概念)或者是否有更优雅的解决方案？

我知道我可以随着搜索深度的增加多次循环遍历 friend 列表，但这将是一个不优雅的解决方案，需要很长时间处理大量数据。

我已经很了解 A* 等寻路算法，但我只是不确定这是否适合它们

程序至少应该输出一个字符串，例如“从 person1 到 person2 需要 x 步”。如果能认识中间人，甚至可能从中获得一个不错的网络/图表，那就太好了。

Answer 1

此链接Finding Paths in Graphs (第 33,34 页)为您提供了一种强大的图算法，您可以假设这些图是小世界图!

在实现该算法之前，您应该将 json 数据转换为具有合理快速数据结构的图形(密集与稀疏图形表示)。