查找图直径的时间复杂性

cs.stackexchange https://cs.stackexchange.com/questions/194

题

找到图$ g =（v，e）$的直径的时间复杂性是多少？

  • $ {o}（| v |^2）$
  • $ {o}（| v |^2+| v | cdot | e |）$
  • $ {o}（| v |^2 cdot | e |）$
  • $ {o}（| v | cdot | e |^2）$

图$ g $的直径是图中所有顶点之间最短路径距离集的最大值。

我不知道该怎么办，我需要对如何解决这样的问题进行完整的分析。

有帮助吗？

解决方案

更新：

该解决方案不正确。

不幸的是，该解决方案仅适用于树木！找到树的直径甚至不需要。这是图形的反例（直径为4，如果选择此$ V $，则算法返回3）：

enter image description here

如果该图是指的，这很复杂， 这是一些纸 在致密情况下，声称比在最短路径上使用算法更快。

但是我的要点是图表是 不是 导演和非负性的造成物，我多次听说过一个不错的技巧：

  1. 选择一个顶点$ v $
  2. 查找$ u $，以至于$ d（v，u）$是最大的
  3. 查找$ w $，以至于$ d（u，w）$是最大的
  4. 返回$ d（u，w）$

它的复杂性与两个连续的广度首次搜索¹相同，即如果该图已连接到$ O（| e |）$。

这似乎是民俗的，但现在，我仍在努力获得参考 或者 证明其更正。当我实现这些目标之一时，我将更新。我现在很简单，我现在就发布答案，也许有人会更快地得到它。

�如果图形加权， 维基百科 似乎说$ o（| e |+| v | log | v |）$，但我只确定大约$ o（| e | log | v |）$。

²如果未连接该图 $ O（α（| V |））$ 从每个连接的组件中选择一个元素。我不确定这是否有必要，无论如何，您可以决定在这种情况下直径是无限的。

其他提示

我认为你的意思是 直径 $ g $，这是$ g $中发现的最长路径。

可以通过首先找到所有对最短路径并确定发现的最大长度来找到直径。 Floyd-Warshall算法 在$ theta（| v |^3）$ time中这样做。 约翰逊的算法 可以实现以实现$ cal {o}（| v |^2 log | v | + | v | cdot | e |）$ time。

较小的最差的运行时绑定似乎很难实现，因为有$ cal {o}（| v |^2）$距离要考虑和计算sublinear（摊销）时间的距离；看 这里 对于相关的界限。笔记 这个 使用不同方法并获得（稍微）更快的算法的纸。

您也可以考虑代数图理论方法。直径$ text {diam}（g）$是最小整数$ t $ st the矩阵$ m = i+a $具有$ m^t $所有条目的属性，均为非零。您可以通过$ O（ log n）$迭代找到矩阵乘法的$ t $。然后，直径算法需要$ o（m（n） log n）$时间，其中$ m（n）$是矩阵乘法的限制。例如，通过Vassilevska Williams对Coppersmith-Winograd算法的概括，直径算法将以$ O（N^{2.3727} log n）$运行。有关快速介绍，请参阅Fan Chung的书中的第3章 这里.

如果将注意力限制在合适的图类类中，则可以在最佳$ O（n^2）$时间中解决APSP问题。这些类包括至少间隔图，圆形弧形图，置换图，两部分排列图，强烈的和弦图，弦式二分图，距离 - 遗传图和双弦图。例如，请参阅 Dragan，FF（2005）。估计受限图家族中所有最短路径：统一方法。算法杂志，57（1），1-21 以及其中的参考。

假设：
1.图未加权
2.图形定向

o（| v || e |）时间复杂性。

算法：

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

解释：
我们检查周期。如果图包含循环，那么我们会继续在循环中移动，因此我们将拥有无限的距离。我们检查是否有连接。如果未连接图，则表示G2中的顶点u从g1到顶点v。其中G1和G2是未连接的任何两个子图。因此，我们将再次有无限的距离。我们将使用BFS计算给定节点（U）与所有其他节点（V）之间的最大距离，这些节点可从U到达。然后，我们将最大程度地计算出先前计算的直径，并由BFS返回。因此，我们将具有当前最大直径。

运行时间分析：

  1. o（| e |）使用DFS
  2. o（| e |）使用DFS
  3. BFS在O（| e |）时间中运行。
  4. 我们必须为每个顶点调用BFS函数，因此总共需要O（| V || E |）时间。

总时间= o（| v || e |） + o（| e |） + o（| e |）
由于| v || e | > | e |
因此，我们有O（| V || e |）的运行时间。

BFS
DFS

注意：这不是解决此问题的优雅解决方案。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top