15、最小生成树之kruskal算法
最小生成树两个重要的算法:Prim 和 Kruskal。
Prim:时间复杂度O(n^2),适用于边稠密的网络。
Kruskal:时间复杂度为O(e*log(e)),适用于边稀疏的网络。
kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O(eloge)的排序算法时,克鲁斯卡算法的时间复杂度即为O(eloge),因此当带权图的顶点个数较多而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果最好!Kruskal
从所有边中找到一个最小的边,且将改变放入后不会生成圈,重复n-1次后求出最小生成树。我们首先将所有边排序,然后从小到大判断,如果不产生圈就加入树中,当加入n-1条边时停止。为了判断是否组成圈,我们要用到并查集,相关知识可以在本站或任一本竞赛书中找到,这里不赘述。算法复杂度是(eloge+eα),α是做一次并查集的复杂度,可以认为是常数。
/*
并查集的一个特性:
用一个数组p[]表示每一个元素的父级元素
最父级的元素的父级元素是一个负数,这个负数的绝对值是这个集合下的元素的个数
*/
#include
#include
usingnamespace std;
constint N=1001; //定义能处理的最大点的个数
template
structEdge
{
int from;
int to;
T cost;
};
template
booloperator <(const Edge
{
return a.cost } /*
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。