在线性时间内再生最小跨越树

Question

如果有一个带有v顶点和e边缘的图G，我已经知道它的最小跨度树T，然后如果采取了E的某些边缘，并且其权重为增加了50，这些边缘可能在最小跨树中可能不在。牢记上述情况，是否有一种方法可以在线性时间内再生一棵新的最小跨越树？注意：重新修改的边缘数量仅为5。

Answer 1

您可能想在此处查看SO问题。我相信这是Szpira＆amp;的本文直接解决的。PAN，可以在O（n）时间进行。