查找从另一个人到另一个人所需的人数

以下是问题设置：您在社交网络上选择一个随机人（A），例如Facebook，然后在Facebook上选择另一个随机人（B）。假设你有权访问每个人的朋友列表，你如何找到从A到达B所需的人数。例如： A是C，V，T，Y，Z的朋友 C是朋友与V，T，A，L V与C，A，Q，W的朋友 T与C，A，Q，B的朋友Y和Z也有一些朋友。答案是这样的，因为A-> T-> B查找从另一个人到另一个人所需的人数

什么是解决这个问题的有效方法？

来源

2016-03-15 mantrarush

取决于您的数据表示。一般情况下，你想找到从A到B的最短路径。 –

没错，除了我觉得在列表中找到一个链接之前，通过列表遍历列表很繁琐。 – mantrarush

Dijkstra算法。您只需要将关系表示为图形。

来源

2016-03-15 15:38:31 MasterID

BFS会更简单快捷。 – beaker

甚至可能是双向BFS，因为朋友图中的分支因子通常非常高。 –

查找从另一个人到另一个人所需的人数

回答

相关问题