我想检验“小世界”或“六度分离”假说,即任何人都可以通过 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 步”。如果能认识中间人,甚至可能从中获得一个不错的网络/图表,那就太好了。
最佳答案
此链接Finding Paths in Graphs (第 33,34 页)为您提供了一种强大的图算法,您可以假设这些图是小世界图!
在实现该算法之前,您应该将 json 数据转换为具有合理快速数据结构的图形(密集与稀疏图形表示)。
关于javascript - 如何找到两个抽象节点之间的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32877440/