算法描述：
一个图的生成树是一个树并把图的所有顶点连接在一起图有许多不同的生成树。 最小生成树实际上是最小权重生成树的简称。
最小生成树具有[ v1 ]边。 其中v是给定图表的顶点数。
Kruskal算法是一种贪婪算法。 贪婪的选择是选择最小权重的边缘，不会与当前生成树形成循环。
算法步骤：
1 )按所有边的权重排序(从小边到大边) 2、选择最小边。 检查是否与当前生成树形成循环。 如果未形成循环，请将此边添加到生成树中。 否则，把它扔掉。 3 )重复步骤2，直到生成树(V-1 )有边缘需要下图中的最小生成树(MST :最小生成树)
此图有9个节点，14条边，MST有8条边。
按权重对每个边进行排序，如下所示： 从小到大排序。
weightsrcdest 1762822654014256867237880781293410541171435然后选择边。
选择了V-1边。 算法将退出。
时间复杂度：
o(eloge )或O(ElogV )。 因为对使用o(eloge )的时间进行排序，然后在遍历中使用o ) O(LogV )，所以总复杂度为o ) elogeelogv )。 因为e的值最大是V^2
可以将o(logv )和O(LogE )视为相同。
算法实现：
//Kruskal算法有向图的最小生成树# include iostream # include stdlib.husingnamespacestd； //加权结构struct Edge{ int start； int end； 输入权重； (； //无向图structgraph(//v-顶点个数E-边个数int V，e； //图是用由边构成的排列表示的//无向图，因此是从start到end的边，同时也是从end到start的边。 按边计算struct Edge* edge； (； 构造//v个顶点的e条边的图structgraph*creategraph(intv，int E ) struct graph * graph=(struct graph * ) malloc ) sizeof ) structgraph graph-E=E； graph-edge=(structedge* ) malloc ) graph-e*sizeof ) structedge )； 返回图形； (； //集合的结构体struct subset{ int parent； int rank； (； //使用路径压缩，将元素I所在的集合intfind(structsubsetsubsets[]，int i ) ) if ) subsets[I].parent！=i ) subsets[i].parent=find(subsets，subsets[I].parent )； } return subsets[i].parent； //按等级x，yvoidunion (structsubsetsubsets [ ]，int x，int y ) ) intxroot=find ) subsets，x )； intyroot=find(subsets，y )； //将等级小的树作为等级大的树下的端if (subsets [ x root ].rank subsets [ y root ].rank ) { subsets[xroot].parent=yroot； } else if (subsets [ x root ].rank subsets [ y root ].rank ) { subsets[yroot].parent=xroot； } //If ranks are same，thenmakeoneasrootandincrement//itsrankbyoneelse { subsets [ y root ].parent=x root； subsets[xroot].rank； }//对边intCMP(constvoid*a，const void* b ) ) structedge*B1=(structedge* ) a )进行加权比较return a1-weight b1-weight； }//Kruskal算法voidkruskalmst (struct graph * graph ) ) { int V=graph-V； struct Edge result[V]； //保存的最小生成树int e=0； //result[]的索引int I=0； //已排序边缘的索引//step 1:按从小到大的顺序依次选择图形边缘[0]、CMP (graph-edge、graph-e、sizeof )； //并行检查集中的内存structsubset * subsets=(struct subset * ) malloc ) v*sizeof ) struct subset ) )； //初始化和校验//用单个元素构造v个集合for (intv=0； vV； v ) { subsets[v].parent=v； subsets[v].rank=0； //边数小于V-1时一直添加，直到V-1结束为止，在while(ev-1 ) { //Step 2:中先选择最小权重的边，且选择istructedgenext _ edge=graph-edge (ge ) intx=find(subsets，next_edge.start； inty=find(subsets，next_edge.end； //如果在这一带不发生循环(根据并列判断)//将添加到result中，而且是Eif(x！=y({result[e]=next_edge； union(subsets，x，y )； (/)否则放弃，打印(/)/result [ ] cout ' followingaretheedgesintheconstructedmst ' endl； for(I=0； i e； I } { cout result [ I ].start '-- ' result [ I ].end '=' result [ I ].weight endl； }}int main (()/*创建下图。 10---3---1|(|6|5 (|15|(|2-----3 )/intv=4； //顶点数int E=5； //边数struct graph * graph=create graph (v，e )； //边0-1 graph-edge[0].start=0； graph-edge[0].end=1； graph-edge[0].weight=10； //边0-2 graph-edge[1].start=0； graph-edge[1].end=2； graph-edge[1].weight=6； //添加边0-3 graph-edge [2].start=0； graph-edge[2].end=3； graph-edge[2].weight=5； //边1-3添加graph-edge [3].start=1； graph-edge[3].end=3； graph-edge[3].weight=15； //添加边2-3 graph-edge [4].start=2； graph-edge[4].end=3； graph-edge[4].weight=4； kruskalMST(graph )； 返回0； }执行结果：
followingaretheedgesintheconstructedmst2---3==40---3==50---1==10参考： http://www.geeksforgeks.org