5 algorithm graph-theory graph-algorithm
我只是在学习图论,我正在尝试将代码写入算法问题.问题涉及n群人,他们每个人与其中一个成员至少有一个相互的友谊.问题是要找到两个人之间最短的友谊关系.最短的友谊链接包含最少的人数.例如; A和B是共同的朋友,B和C是共同的朋友,如果A和C也是共同的朋友,那么AC和ABC是A和C之间的友谊链接但AC被认为更短,因为它涉及较小的个体.
我想知道哪种图理论算法适用于这种情况,我将不胜感激任何关于图论(免费维基)的免费互联网文档的建议.
对于两个节点的最短路径的未加权问题 - 你可以使用BFS,不需要Dijkstra的算法,这种算法更难实现并且效率较低.
请注意,BFS的主要问题是空间效率,因为它在O(|V|)空间中运行,可以通过与DFS(称为迭代深化DFS)的权衡来部分解决.它也是最佳的,但会消耗更少的空间(以额外的时间为代价).
似乎并非如此,但是如果你可以评估你与目标的接近程度 - 你可以使用A*算法,它具有良好的启发式功能可能会更快地执行.
另请注意:如果您想要所有用户之间的最短距离,您可以使用Floyd-Warshall的算法
| 归档时间： |
|
| 查看次数： |
6348 次 |
| 最近记录： |