algorithm - 在给定旧 MST 和新顶点 + 边的情况下查找最小生成树

Question

在示例问题中，我得到了加权图 G = (V, E) 的 MST T。问题是，如果要将一个新顶点 v 及其所有边添加到图中，什么是 o(|V|log|V|) 算法来计算这个新 G* = (V U 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|)

我该怎么做？

Answer 1

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

复杂度是新增边数的(n+m)倍(大致呈线性)。