图的边权值都在1到n的整数范围内，设计O(n(V+E))算法来找出最小生成树

V代表点，E代表边，假设一个图的边权值都在1到n的整数范围内，如何设计出一种O(n(V+E))的算法来找出这个图的最小生成树呢？因为要找的算法是O(n(V+E))，所以传统的kruskal和prim's不符合这个时间复杂度。有没有什么算法思路可以用O(n(V+E))来找最小生成树呢？非常感谢！！！

555555求解

和kruskal一样的思想，用一个i枚举1-n，每次枚举所有边并找出其中权值为i的（如果硬要凑这个复杂度只能这么找了，其实有点傻），如果边i对应的两个点中有点没有加入生成树，就把这条边加入，否则pass。

除非所有的边都已经排好序，否则没可能。

孙行者 发表于 2020-5-5 03:58
除非所有的边都已经排好序，否则没可能。

权值都是1到n的话，可以countin sort，其实就是O（n）复杂度。。

不知道楼主解决没有，prim其实每次都是拿最小的出来，因为你的权值是1到n，其实你可以用一个array之类的存下来每个权值等于i的边，然后依次处理就行了。类似于counting sort

不知道小帅 发表于 2020-6-3 11:49
权值都是1到n的话，可以countin sort，其实就是O（n）复杂度。。

对啊！我咋就没审出这个关键？！牛啊！