algorithm - 我们可以在每个顶点上使用 BFS 来找到图形的直径吗？如果是这样，这是最好的解决方案吗？

Question

所以我发现了一个老话题:

Algorithm for diameter of graph?

他们说非稀疏图的最佳解决方案是 O(V^3)

但我们不能只在每个顶点上使用 BFS 然后找到最大值吗？这样时间复杂度将是 O(V*(V+E)) = O(V^2 + VE)我错了吗？因为如果边的数量只是 V 的被乘数，那么这会更好，对吧？

所以我想我的问题是:

1. 截至 2018 年，计算图形直径的最佳时间复杂度是多少

2. 是我的方法错了吗？我在这里缺少什么？

Answer 1

有问题的矩阵是非稀疏的。所以它给出了最坏情况 E ~ (V^2)/2 边。因此，对于非稀疏矩阵，所提到的解决方案将变为 O(V^2+V*(V^2)) 。

如果矩阵是稀疏的，那么它确实比 O(V^3) 更快。

此外，鉴于图形是非稀疏的，通常使用邻接矩阵表示它，以加快查找时间。因此广度优先搜索需要 O(V^2)。正如您提到的那样，跨所有节点完成此操作将再次导致 O(V^3) 计算时间复杂度。

找到直径可以通过首先找到所有对最短路径并确定找到的最大长度来完成。 Floyd-Warshall algorithm在 O(V^3) 时间内完成。 Johnson's algorithm可以实现O(V^2 logV + VE)的时间。