本文介绍了寻找最小生成树给老MST和一个新的顶点+边缘的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在一个样本的问题,我给出一个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和一个新的顶点+边缘的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-09 18:12