2

在一个示例问题中，我得到了一个加权图 G = (V, E) 的 MST T。问题是，如果要将一个新顶点 v 及其所有边添加到图中，那么计算这个新 G* = (VU v, E*)。

到目前为止，我唯一的想法是：

add min( out(v) ) to T
for each edge e in out(v) do
  let u be the other vertex of e
  if there exists a lower weight path from v to u then
    remove all edges in that path from T
    add e to T

两个问题：

  1. 如何处理可能已断开连接的顶点
  2. 这绝对不是 O(|V|log|V|)

我怎样才能做到这一点？

4

2 回答 2

2

您也可以在线性时间内完成（如果新边的数量（例如 k）与 n 相比要少得多）。我们知道新的 MST 应该覆盖新的顶点。因此，必须添加至少一条新边。因此必须将具有最小值的边添加到MST（您可以证明这一点）；可能会发生不止一个新的边缘发生变化。所以按升序对新边进行排序将第一个添加到图中；现在我们有了一个新的循环。进行图遍历找到循环并从该循环中删除具有最大值的边。现在添加另一个新边并重复该过程。

复杂度是 (n+m) 乘以新添加的边数（大致线性）。

于 2013-02-24T23:12:41.060 回答
0

看到最终你知道你的 MST 将在 th MST 中的边缘和添加的新边缘之间

因此，添加所有新边，您将得到一个图表。对此执行任何正常的 MST 算法（Boruvka、Kruskal、Prims），您将获得解决方案。

由于其中的边缘 = (V-2) 最初添加的 (V-1) = 2V-1，因此算法将达到您需要的时间限制。

于 2012-01-29T19:17:03.937 回答