我们可以在每个顶点上使用BFS来找到图的直径吗？如果是，这是最好的解决办法吗？
我们可以在每个顶点上使用BFS来找到图的直径吗？如果是，这是最好的解决办法吗？
提问于 2018-03-19 16:33:08
所以我找到了一个老话题：
非稀疏图的最佳解是O(V^3)。
但是，我们不能只在每个顶点上使用BFS，然后找到最大值吗？这样的时间复杂度是O(V*(V+E)) = O(V^2 + VE)，我错了吗？因为如果边数只是V的乘数，这会更好，对吗？
所以我想我的问题是：
- 到2018年为止，计算图形直径的最佳时间复杂度是什么？
- 是我的方法错了吗？我在这里少了什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-03-19 17:10:20
所讨论的矩阵是非稀疏。给出了E~ (V^2)/2边的最坏情形。因此，上述解将成为非稀疏矩阵的O(V^2+V*(V^2)) .
如果矩阵是稀疏的，那么它确实比O(V^3)更快。
另外，如果图是非稀疏的，则通常使用邻接矩阵表示，以加快查找时间。因此，宽度优先搜索需要O(V^2)。正如您在所有节点上提到的那样，这将再次导致O(V^3)计算时间复杂性。
找到直径可以通过先找到所有对最短路径和确定找到的最大长度来完成。Floyd-Warshall算法在O(V^3)时间内这样做。约翰逊算法可以实现O(V^2 logV + VE)时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49367939
复制相关文章
相似问题
腾讯云开发者
