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

Question

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

我得到了一个图形G =（V，E）。它是已连接的无向加权图。该图由生成树和一条边组成。我将如何使用一种算法来计算n = | V |中的图形的MST时间复杂度。我在想Kruskal的算法，但它不能满足时间复杂度的要求。

Answer 1

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