【转】最小生成树——Kruskal算法标记(以空格分隔) :算法
本文转载。 原文为最小生成树算法和Kruskal算法，重试时只需Kruskal算法，因此在此不涉及Prim算法。 根据需要请参考原文。
Kruskal算法1 .概述Kruskal算法是一种用于查找最小生成树的算法，由Joseph Kruskal于1956年发表。 为了解决同样的问题，有Prim算法和Boruvka算法等。 三种算法都是贪婪算法的应用。 与Boruvka算法的不同之处在于，Kruskal算法在图中存在相同权重的边缘时也有效。
2 .算法的简要说明1 ) .记住Graph有v个顶点，e个边
2 )新的图表Graphnew，Graphnew有与原图表相同的e个顶点，但是没有边
3 )将原图Graph的所有e个边按照权重从小到大的顺序进行排序
4 )循环)从权重最小的边横贯各边，直到图表Graph的所有节点都在同一连通分量上
连接有边if的两个节点在图表Graphnew的图例中说明，而不是在图表Graphnew中将边添加到同一合并分量中。
首先，第一步是有几个点和边的Graph图
对所有边的长度进行排序，并将排序的结果作为边选择的依据。 这里再次出现了贪婪算法的思想。 对资源进行排序，选择局部最优资源，排序完成后，我们率先选择了边缘AD。 这样我们的图就变成了右图
在剩下的边里找。 我找到了CE。 这里的权重也是5
按顺序找到了6、7、7，即DF、AB、BE。
然后，继续选择BC或EF，尽管当前长度为8的边是最小的未选定边。 但是，现在他们已经连接上了(对于BC可以用CE、EB连接，同样的EF可以用EB、BA、AD、DF连接)。 所以没有必要选择他们。 类似的BD也已经连接上了。 (这里上图中的连通线用红色表示。
最后剩下EG和FG。 当然我们选择了EG。 最后成功的图是右边：
3 .总结kruskal算法在图中的顶点数n，简要证明kruskal算法适用于任意n次图。
摘要基础：
n=1，很明显可以找到最小生成树。
汇总流程：
假设Kruskal算法适用于nk次图，在k 1次图g中，通过将最短边的端点a和b合并为一个合并操作，即把u和v作为一个点v’，把与u和v相接的边全部连接到v’上，可以得到
我们证明T' {u，v}是g的最小生成树。
在反证法中，如果T' {u，v}不是最小生成树，则最小生成树为t，即w(t ) w ) T' {u，v} )。 显然t应该包括u，v，否则u，v加上t形成循环，删除循环上原来的任意一边，形成权重较小的生成树。 T-{u，v}是g的生成树。 所以w(t-{u，v} )=w ) t ) )，也就是说w ) t )=w ) t ) ) w ) u，v ) )产生了矛盾。 这样假设不成立，T' {u，v}是g的最小生成树，Kruskal算法也适用于k 1次图。
由数学归纳法、Kruskal算法证明。
4 .代码算法为typedef struct { char vertex [ vertex num ]； //顶点表int edges[VertexNum][VertexNum]； //邻接矩阵由边表int n，e； //图中当前顶点数和边数}MGraph； typedef struct node { int u； //边的开始顶点int v； //边的终端顶点int w； //边缘权重(}Edge； voidkruskal(mgraphg ) intI，j，u1，v1，sn1，sn2，k； int vset[VertexNum]； //辅助数组，判定两个顶点是否连接int E[EdgeNum]； //保管所有边k=0； //E数组的下标从0到for(I=0； iG.n； I ) for(j=0； jG.n； j () if ) g.Edges[I][j]！=0 G.edges[i][j]！=INF(e[k].u=I； E[k].v=j； E[k].w=G.edges[i][j]； k； }}heapsort(e，k，sizeof ) e[0] )； //按堆积排序，按照权重从小到大的顺序排列for (I=0； iG.n； I//辅助数组初始化{ vset[i]=i； (k=1； //生成的边数最后正好成为总边数j=0； //E中的下标while(kg.n ) ) { sn1=vset[E[j].u]； sn2=vset[E[j].v]； //得到两顶点所属的集合号if(sn1 )！=sn2 )//如果不在同一个集合号内，则将边设置为最小生成树(printf(%d----%d，%d )、E[j].u、E[j].v、E[j].w )； k； for(I=0； iG.n； I ) if(vset[I]==sn2 ) { vset[i]=sn1； }}j； }