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

问题描述：

在示例问题中，给出加权图G =（V，E）的MST T.问题是，如果一个新的顶点v及其所有边被添加到图中，什么是o（| V | log | V |）算法来计算这个新的G *的新MST =（VU v， E *）。在给定旧MST和新顶点+边缘的情况下查找最小生成树

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

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

两个问题：

什么我可能已经得到了断开
顶点做这绝对不是O（| V | log | V |）

我该怎么做？

为什么要从一个循环的一条腿上移除所有边缘？只删除最大重量的一个边缘。 – phs

提示：修改[Borůvka的算法]（http://en.wikipedia.org/wiki/Boruvka%27s_algorithm）。 – Per

答

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

因此，添加所有新的边缘，你会得到一个图形。对此做任何正常的MST算法（Boruvka，Kruskal，Prims），你将得到你的解决方案。由于其中的边是=（V-2）最初（V-1）加上= 2V-1，算法将实现你所需要的时间限制。

答

你也可以在线性时间内做到这点（如果新边的数量（比如k）比n小得多）。我们知道新的MST应该覆盖新的顶点。所以至少必须添加一个新的边缘。因此，必须将最小值的边添加到MST中（可以证明这一点）;它可能发生不止一个新的边缘改变。所以从升序排序新边缘将第一个边添加到图中;现在我们有一个新的循环。执行图遍历查找循环并从该循环中删除具有最大值的边。现在添加其他新边缘并重复该过程。

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

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

相关推荐