算法-朋友的朋友
算法-朋友的朋友
提问于 2013-02-28 16:30:29
我只是在学习图论，我试着把代码写成一个算法问题。这个问题涉及到n群体，他们每个人至少有一个与其中一个成员的相互友谊。问题是找到两个人之间最短的友谊联系。最短的友谊环节包含的人数最少。例如，A和B是共同的朋友，B和C是共同的朋友，如果A和C也是共同的朋友，那么A-C和A-B-C是A和C之间的友谊纽带，但是A-C被认为更短，因为它涉及较小的个体。
我想知道哪种图论算法在这种情况下适用，我希望任何关于图论的免费互联网文档的推荐(维基除外)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-02-28 16:47:36
对于两个节点最短路径的未加权问题，您可以使用BFS，而不需要更难实现和效率较低的Dijkstra's algorithm。
请注意，BFS的主要问题是空间效率，因为它在O(|V|)空间中运行，因此可以通过与称为Iterative Deepening DFS的DFS进行折衷来部分解决。它也将是最佳的，但将消耗更少的空间(以额外的时间为代价)。
情况似乎并非如此，但如果您能够评估您与目标的距离有多近--您可以使用 Algorithm，因为heuristic function的执行速度可能会更快。
还请注意:如果您希望所有用户之间的距离最短，可以使用Floyd-Warshall's algorithm
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15140677
复制相关文章
相似问题
腾讯云开发者
