【克鲁斯卡尔算法求最小生成树】最小生成树普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储...

【克鲁斯卡尔算法求最小生成树】最小生成树普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储...

【答案】 kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O（eloge）的排序算法时,克鲁斯卡算法的时间复杂度即为O（eloge）,因此当带权图的顶点个数较多而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果最好!
　　克鲁斯卡尔算法
　　假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林.之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树；反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之.依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止.
　　普里姆算法
　　假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合.显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集.在算法开始执行时,TE 为空集,TV 中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有 n-1条边为止.
　　1.Kruskal
　　#include
　　#include
　　#include
　　using namespace std;
　　struct node
　　{
　　int v1;
　　int v2;
　　int len;
　　}e[10000];//定义边集
　　int cmp(const void *a,const void *b)//快排比较函数
　　{
　　return ((node*)a)->len-((node*)b)->len;
　　}
　　int v[100],a[100][100];//v为点集
　　void makeset(int n)
　　{
　　for(int i=0;i

哦，回答的不错

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息