对于有n个顶点，m条边的图，求解最小生成树问题的Kruskal算法，其时间复杂性是多少？

Question

在网上学算法的时候弹出来的一道题目
对于有n个顶点，m条边的图，求解最小生成树问题的Kruskal算法，其时间复杂性是多少？
A : mlogm
B : nlogn
C : n^2logn
D : mlogn
这个题选择A,C,D
A选择很好理解, C和D该怎么想呢?

Answer 1

Kruskal算法的核心就是把图中所有的边从小到大遍历，然后对于遍历到的每一个边，只要它不构成回路，就把它加入答案中。对这些边排序的效率很可能是mlogm，所以A确实没啥问题。

然而我们总需要判断一条边是否构成回路。Kruskal的方法是，在一开始的时候把每一个顶点都作为一棵二叉树的根，它们的父节点都是自己（这一步效率是n，不用理它）。然后当我遍历到某个边的时候，我只要看这条边的两个顶点有没有共同的祖先就好了，如果有，这条边就构成回路，如果没有，说明这两个顶点分别在两棵树里，就把这条边加入答案中，然后把比较短的那棵树的根的父节点设为比较长的那棵树的根，这样就把短的树接到长的树上面了。因为到最后树最多有logn层，所以搜索一个顶点的根和把两棵树接到一起的效率就是logn。因为我们对于每一条边都要搜索两次顶点，所以这里的效率就是mlogn，D答案就是这么想。

然后我们需要做n-1次把树接到一起的工作，所以接树的效率当然是nlogn。完全不理解C怎么可能是对的。我不知道那道题在哪里，但估计是用盗版的Xcode做的。

把流程给你看看好了。