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

Question

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

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

Answer 1

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