寻找最小生成树给老MST和一个新的顶点+边缘 [英] Finding a Minimum Spanning Tree given the old MST and a new vertex + edges

问题描述

在一个样本的问题，我给出一个MST T代表一个加权图G =（V，E）。的问题是，如果一个新的顶点v和所有其边缘是要加入到图中，什么是邻（| V |登录| V |）算法来计算这个新G * =（VU的v的新的MST， E *）。

In a sample problem, I'm given a MST T for a weighted graph G = (V, E). The question is, if a new vertex v and all its edges are to be added to the graph, what is an o(|V|log|V|) algorithm to compute the new MST of this new G* = (V U v, E*).

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

My only idea so far is:

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 |登录| V |）

我怎样才能做到这一点？

How can I do this?

推荐答案

请参阅最后你知道你的MST将是已经在MST边缘和新边加入其中。

See ultimately you know that your MST will be among the edges already in the MST and the new edges added.

所以添加的所有新的边缘，你会得到一个图表。做任何正常的生成树算法（Boruvka，秩，Prims）就这个问题和你有你自己的解决方案。

So add all the new edges you will get a graph. Do any normal MST algorithm (Boruvka, Kruskal, Prims) on this and you will have your solution.

由于在该边缘被=（V-2）首先（Ⅴ-1）中加入= 2V-1算法将实现需要约束时。

Since the edges in this is = (V-2) Initially (V-1) added = 2V-1 the algorithms will achieve the time bound you need.

这篇关于寻找最小生成树给老MST和一个新的顶点+边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！