LinkedIn 有一个很酷的功能,在访问某些用户的个人资料时,LinkedIn 会提示您如何通过网络连接到该用户。
假设访问者和个人资料所有者是图中的两个节点,其中节点代表用户,边代表友谊,一个简单的解决方案可以是从两个节点开始到某个级别的 bfs,看看是否有任何交叉点。交叉点将是网络链接节点。
虽然这听起来很简洁,但问题是为了确定每个人的朋友,需要单独的数据库查询。当网络深度超过 2 层时,这将是一个非常耗时的算法。有没有更有效的替代方案?如果没有,我们如何添加更好的硬件支持(并行计算、网格、分布式数据库等)以减少计算所需的时间?