图的克鲁斯卡尔算法

‘壹’ 如何实现克鲁斯卡尔算法

最好结合具体题目实现，我这里有个题目，里面有完整的代码，慢慢理解就是了 http://blog.csdn.net/aihahaheihei/article/details/6751786
里面还有很多，感兴趣也可以看看

‘贰’ 数据结构中图的克鲁斯卡尔算法的基本思想是

基本思想是：设有一个有n个顶点的连通网络N=｛V，E｝，最 初先构造一个只有n个顶点，没有边的非连通图 T=｛ V，￠｝，图中每个顶点自成一个 连通分量。当在E中选到一条具有最小权值的边时，若该边的两个顶点落在不同的连通 分量上，则将此边加人到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复 下去，直到所有顶点在同一个连通分量上为止。

‘叁’ 克鲁斯卡尔时间复杂度怎么算出来的

Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。

kruskal算法：

求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
棵树的一个森林。之后，从网的边集 E
中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

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

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

‘伍’ 克鲁斯卡尔算法的时间复杂度为多少

时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。

基本思想是先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树。

反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

(5)图的克鲁斯卡尔算法扩展阅读：

克鲁斯卡尔算法证明

假设G=(V,E) 是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取。

若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。

克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。

‘陆’ 克鲁斯卡尔算法求最小生成树

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：
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：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

‘柒’ 克鲁斯卡尔算法的基本思想

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。时间复杂度为为O(e^2), 使用并查集优化后复杂度为 O（eloge），与网中的边数有关，适用于求边稀疏的网的最小生成树。

‘捌’ 什么是克鲁斯卡尔算法

设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V, E},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。2算法描述编辑克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至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]

‘玖’ 克鲁斯卡尔算法的介绍

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