如何在 |V| 中找到图的 MST给定生成树加上另一条边的时间

Question

我想知道如何着手解决这个问题。

我得到了一张图表 G = (V,E)。这是一个连通的无向加权图。
该图由一棵生成树和一条附加边组成。
我如何想出一种算法来计算图的 MST n = |V| 时间复杂度。
我在想克鲁斯卡尔算法，但它不符合时间复杂度要求。

Answer 1

一棵生成树加上一条边正好形成一个循环。使用深度优先搜索找到循环，然后删除其最重的边缘。