克鲁斯卡尔2014数据结构高分笔记的克鲁斯卡尔算法，没看懂。 getRoot函数那个是怎么做到的？

普里姆与克鲁斯卡尔算法有什么区别

克鲁斯卡尔算法： 是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

。

普里姆算法： 同样是在未选取的边中寻找最小边，但是选取的原则多了一条，就是该边必须和已选取的边相连，比如，如果边(1, 2)已被选取，那么接下来选取的边，必须是和顶点1，或者顶点2相连的。

。

就是这样。

。

如图所示：

什么是克鲁斯卡尔算法

BlueSky2008说的是克鲁斯卡尔算法，算法复杂度为O(n^2*logn) Prim算法是从点出发，选择与点集相连最短的边，然后从点来扩展，需要通过内存来存储已经选择的点集，但时间复杂度低，复杂度为O(n^2)。

Kruskal算法是从当前边集的最短边出发，这里要考虑到边的排序，排序复杂度为O(nlogn)，计算n次，因此复杂度为O(n^2*logn)。

因此Prim算法总的效率比Kruskal算法高。

详见： /javado/archive/2006/07/15/10050.aspx

什么是克鲁斯卡尔算法

设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V, E},图中每个顶点自成一个连通分量。

当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。

如此重复下去，直到所有顶点在同一个连通分量上为止。

2算法描述编辑克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

克鲁斯卡尔算法从另一途径求网的最小生成树。

假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。

在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。

依次636f707962616964757a686964616f31333335323535类推，直至T中所有顶点都在同一连通分量上为止。

例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。

代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。

因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。

因此，构造成一棵最小生成树。

上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次需O（e））。

又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。

[1]

克鲁斯卡尔算法是求图的什么

求图的最小生成树啊，你上面不是也讲了么？ 求最小生成树还有另一种prim算法 prim适合用于稠密图，kruskal适合用于稀疏图 两种算法都是以贪心为基本思想的~ 满意望采纳谢谢！！！！

请用克鲁斯卡尔算法为下图构造最小生成树，谢谢。

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考： 1：将图中的n顶点看成是n个集合。

解释为，图中共有6个顶点，那么就有六个集合。

即a,b,c,d,e,f各自分别都是一个集合。

｛a｝,｛b｝等。

2：按权值由小到大的顺序选择边。

所选边应满足两个顶点不在同一个顶点集合内。

将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。

这是书上的描述，可能有点难理解，这里解释一下： 首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝ 3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下： 此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。

新的顶点集合为｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝ 接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝ ｛d,f｝ ｛b,e｝ 继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝ ｛b,e｝ 再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！ 4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

2014数据结构高分笔记的克鲁斯卡尔算法，没看懂。 getRoot函数那个是怎么做到的？

例： int FindRoot(int a) { if(Tree[a]==-1)//没有父节点，返回a return a; else { int tmp=FindRoot(Tree[a]);//存在父节点，递归返回离根最近的父节点id Tree[a]=tmp;//将自己的父节点修改为最直接的父节点，使树变矮，优化 return tmp;//返回父节点 } } 不知道高分笔记的克鲁斯卡尔算法具体怎么实现，但是原理如上