计算“凯文·培根”数

这是一个标准 shortest path problem . 有很多解决方案,包括 Dijkstra's algorithm Bellman-Ford . 您可能对查看 A* algorithm 看看它将如何执行与任何特定节点度的倒数相关的代价函数。我们的想法是首先访问更受欢迎的节点(那些拥有更高学位的节点)。

听起来像是一份工作 Dijkstra's algorithm .

艾德:呃,我不该这么快扣动扳机。当权重为1时,Dijkstra(和Bellman Ford)的搜索减少为广度优先搜索,因此这不太有用。哦,好吧。

A* algorithm tvanfosson提到的,可能是这方面的理想选择。其思想是,不必按照元素在树的每一层(基于起点或终点)的任何顺序进行搜索和递归,而是使用一些启发式方法来确定要首先尝试的元素。在您的情况下,一个好的赌注可能是节点的度数(“朋友”的数量),但您可能希望使用给定人员任意度数范围内的人数(也就是说,一个有三个朋友,每个朋友都有100个朋友的人可能比一个有20个朋友的人在一个避开外人的小圈子里更容易成为一个节点)。你可以用其他各种东西作为启发(朋友得2分,朋友的朋友得1分;不管怎样,实验)。

结合这一点和深度限制(在6度间隔后切断,或其他),你可以大大改善你的平均情况(最坏情况仍然与基本BFS相同)。

总的来说,这个可能更好 Floyd-Warshall 所有对的最短距离。