大门| 2017年模拟大门|问题24

如果Kruskal算法用于寻找一个加权图G的最小生成树，该图有n个顶点和m条边，边的权重已经在一个排序列表中给出，那么，如果并集和查找操作采用摊销O（1），计算最小生成树的时间复杂度是多少？ （A） O（m logn） （B） O（n）

（C） O（m） （D） O（n logm）

答复: （C） 说明： O（m）因为已经按排序顺序给了边权重。你只需要按递增的顺序选取边，并将其添加到当前的生成集中，如果它的添加不会导致循环，否则就扔掉它。 这个问题的小测验