我们可以在每个顶点上使用 BFS 来找到图形的直径吗？如果是这样，这是最好的解决方案吗？
Can we use the BFS on each vertex in order to find the graph's diameter? if so, is this the best solution?
所以我发现了一个老话题:
Algorithm for diameter of graph?
他们说非稀疏图的最佳解决方案是 O(V^3)
但是我们不能只在每个顶点上使用 BFS 然后找到最大值吗？
这样时间复杂度将是 O(V*(V+E)) = O(V^2 + VE)
我错了吗？因为如果边的数量只是 V 的被乘数，那么这会更好，对吧？
所以我想我的问题是：
2018 年计算图形直径的最佳时间复杂度是多少
是我的方法错了吗？我在这里错过了什么？
有问题的矩阵是non-sparse。所以它给出了最坏情况 E ~ (V^2)/2 边。因此，对于 non-sparse 矩阵，所提到的解决方案将变为 O(V^2+V*(V^2))。
如果矩阵是稀疏的，那么它确实比 O(V^3) 更快。
此外，鉴于图是 non-sparse，它通常使用邻接矩阵表示，以加快查找时间。因此广度优先搜索需要 O(V^2)。正如您提到的那样，跨所有节点完成此操作将再次导致 O(V^3) 计算时间复杂度。
找到直径可以通过首先找到所有对最短路径并确定找到的最大长度来完成。 Floyd-Warshall algorithm does this in O(V^3) time. Johnson's algorithm可以实现O(V^2 logV + VE)的时间。
所以我发现了一个老话题:
Algorithm for diameter of graph?
他们说非稀疏图的最佳解决方案是 O(V^3)
但是我们不能只在每个顶点上使用 BFS 然后找到最大值吗？ 这样时间复杂度将是 O(V*(V+E)) = O(V^2 + VE) 我错了吗？因为如果边的数量只是 V 的被乘数，那么这会更好，对吧？
所以我想我的问题是：
2018 年计算图形直径的最佳时间复杂度是多少
是我的方法错了吗？我在这里错过了什么？
有问题的矩阵是non-sparse。所以它给出了最坏情况 E ~ (V^2)/2 边。因此，对于 non-sparse 矩阵，所提到的解决方案将变为 O(V^2+V*(V^2))。
如果矩阵是稀疏的，那么它确实比 O(V^3) 更快。
此外，鉴于图是 non-sparse，它通常使用邻接矩阵表示，以加快查找时间。因此广度优先搜索需要 O(V^2)。正如您提到的那样，跨所有节点完成此操作将再次导致 O(V^3) 计算时间复杂度。
找到直径可以通过首先找到所有对最短路径并确定找到的最大长度来完成。 Floyd-Warshall algorithm does this in O(V^3) time. Johnson's algorithm可以实现O(V^2 logV + VE)的时间。