很多朋友对于克鲁斯卡尔算法的时间复杂度和普里姆算法时间复杂度不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！
本文目录
一、kruskal算法
1、克鲁斯卡尔算法是求连通网的最小生成树的另一种 *** 。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
2、克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。
3、在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
4、克鲁斯卡尔算法的时间复杂度主要由排序 *** 决定，而克鲁斯卡尔算法的排序 *** 只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序 *** 时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。
二、克鲁斯卡尔算法的算法描述
1、克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
2、克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
3、例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。
4、上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（之一次需O（e））。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。
三、克鲁斯卡尔算法介绍
1、克鲁斯卡尔算法是求连通网的最小生成树的另一种 *** 。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
2、克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
四、克鲁斯卡尔算法是贪心算法吗
1、克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。
2、克鲁斯卡尔算法是求连通网的最小生成树的另一种 *** 。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
3、克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。
4、在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
5、克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。对带权图G中e条边的权值的排序 *** 可以有很多种，各自的时间复杂度均不相同。
6、对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O（elge）。判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个顶点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O（n）。
五、最小生成树 普里姆算法和克鲁斯卡尔算法
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条边为止。
--以上传自
//题目 *** :
int cmp(const void*a,const void*b)//快排比较函数
ret *** n((node*)a)->len-((node*)b)->len;
int v[100],a[100][100];//v为点集
if(!used[j]&& dis[k][j]<d[j])
d[j]= dis[k][j];//与Dijksta算法的差别之处
cout<<prim(n)<<endl;
六、克鲁斯卡尔算法的时间复杂度为多少
1、时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。
2、基本思想是先构造一个只含 n个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树。
3、反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1条边为止。
4、假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取。
5、若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。
6、克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。
7、参考资料来源：百度百科——克鲁斯卡尔算法
七、Kruskal算法的时间复杂度是多少
1、Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
2、求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
3、具有最小耗费的边加入已选择的边的 *** 中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e步，其中e
4、是 *** 中边的数目。按耗费递增的顺序来考虑这e
5、条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的 *** 中会出现环路，则将其抛弃，否则，将它选入。
6、假设WN=(V,{E})是一个含有 n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
7、过程为：先构造一个只含 n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
8、棵树的一个森林。之后，从网的边集 E
9、中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
10、点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
好了，文章到此结束，希望可以帮助到大家。
