有没有一种方法来计算组中包含的任何MST在O（nlogn）的所有边的？
其中，n被定义为| V（G）|
我试图修改的Prim，克鲁斯卡和使用圆财产，但我无法找到任何解决方案。
如果我理解正确你的问题，你想要得到的一组至少出现在一个MST所有边。
显然，算法的运行时间必须下界在所得组边的量。
让我们看一下图Kn（有关详细信息 - https://en.wikipedia.org/wiki/Complete_graph）
有图中的O(n^2)边缘，并设置所有的权重为1。
现在，我们需要的是证明，在图中的每条边至少出现在一个MST，因此算法发现，该组必须由O(n^2)被下界。
证明很简单，让e = (vi,vj)是一个优势，我们可以很容易地构造MST方含e。我们的名字vi, vj - v1, v2 RESP。为简单起见，和所有其他顶点v3, ..., vn。 (v1, v2), (v2, v3), ..., (vn-2, vn-1)是MST。
所以，在这种情况下，所有边缘都在期望的设定，并有O(n^2)边缘，所以算法不能执行O(nlogn)的最坏情况