http://www.51nod.com/
Kruskal算法的高效实现需要一种称作并查集的结构。我们在这里不介绍并查集，只介绍Kruskal算法的基本思想和证明，实现留在以后讨论。
Kruskal算法的过程： （1） 将全部边按照权值由小到大排序。 （2） 按顺序（边权由小到大的顺序）考虑每条边，只要这条边和我们已经选择的边不构成圈，就保留这条边，否则放弃这条边。 算法 成功选择(n-1)条边后，形成一个棵最小生成树，当然如果算法无法选择出(n-1)条边，则 说明原图不连通。 以下图为例： 边排序后为： 1 AF 1 2 DE 4 3 BD 5 4 BC 6 5 CD 10 6 BF 11 7 DF 14 8 AE 16 9 AB 17 10 EF 33 算法处理过程如下： 处理边AF，点A与点F不在同一个集合里，选中AF。 处理边DE，点D与点E不在同一个集合里，选中DE 处理边BD，点B与点D不在同一个集合里，选中BD 处理边BC，点B与点C不在同一个集合里，选中BC处理边CD，点C与点D在同一个集合里，放弃CD。
处理边BF，点B与点F不在同一个集合里，选中BF。 至此，所有的点都连在了一起，剩下的边DF，AE，AB，EF不用继续处理了，算法执行结束。 Kruskal算法的证明。假设图连通，我们证明Krusal算法得到一棵最小生成树。我们假设Kruskal算法得到的树是K (注意我们已经假设Kruskal算法一定可以得到生成树)。假设T是一棵最小生成树，并且K ≠T, K中显然至少有一条边。我们找到在K中，而不在T中最小权值的边e。 把e加入T中，则形成一个圈，删掉这个圈中不在K中的边f,得到新的生成树T’。 f的存在性，如果全里面所有的边都在K中，则K包含圈，矛盾。 考虑边权值关系： （1） 若w(f) > w(e), 则T’的权值和小于T的权值和，与T是最小生成树矛盾。 （2） 若w(f) < w(e), 说明Kruskal算法在考虑加入e之前先考虑了边f，之所以没加入f是因为f和之前加入的边形成圈，之前加入的边权值显然不超过w(f) (因为加边是从小到大的顺序加入的)，所以之前加入的边权值一定小于w(e)。而根据e的定义，K中权值小于w(e)的边都在T中，这说明T中的边会和f构成圈，矛盾。 所以只能w(f) = w(e)。T’仍然是最小生成树，而T’和K相同的边多了一条。 这样下去有限步之后，最终可以把T变为K，从而K也是最小生成树。 最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。 输入 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000) 输出 输出最小生成树的所有边的权值之和。 输入示例 9 14 1 2 4 2 3 8 3 4 7 4 5 9 5 6 10 6 7 2 7 8 1 8 9 7 2 8 11 3 9 2 7 9 6 3 6 4 4 6 14 1 8 8 输出示例 37 请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。 不同语言如何处理输入输出，请查看下面的语言说明。 使用并查集和贪心思想。适合稀疏图。 Kruskal算法实现： [cpp] view plain copy print ? #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int parent[10]; int n,m; int i,j; struct edge{ int u,v,w; //边的顶点，权值 }edges[10]; //初始化并查集 void UFset(){ for(i=1; i<=n; i++) parent[i] = -1; } //查找i的跟 int find(int i){ int temp; //查找位置 for(temp = i; parent[temp] >= 0; temp = parent[temp]); //压缩路径 while(temp != i){ int t = parent[i]; parent[i] = temp; i = t; } return temp; } //合并两个元素a,b void merge(int a,int b){ int r1 = find(a); int r2 = find(b); int tmp = parent[r1] + parent[r2]; //两个集合节点数的和 if(parent[r1] > parent[r2]){ parent[r1] = r2; parent[r2] = tmp; }else{ parent[r2] = r1; parent[r1] = tmp; } } void kruskal(){ int sumWeight = 0; int num = 0; int u,v; UFset(); for(int i=0; i<m; i++) { u = edges[i].u; v = edges[i].v; if(find(u) != find(v)){ //u和v不在一个集合 printf(”加入边：%d %d,权值： %d\n”, u,v,edges[i].w); sumWeight += edges[i].w; num ++; merge(u, v); //把这两个边加入一个集合。 } } printf(”weight of MST is %d \n”, sumWeight); } //比较函数，用户排序 int cmp(const void * a, const void * b){ edge * e1 = (edge *)a; edge * e2 = (edge *)b; return e1->w - e2->w; } int main() { scanf(”%d %d”, &n, &m); for(i=0; i<m; i++){ scanf(”%d %d %d”, &edges[i].u, &edges[i].v, &edges[i].w); } qsort(edges, m, sizeof(edge), cmp); kruskal(); return 0; } /* 测试数据： 7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24 输出： 加入边：1 6,权值： 10 加入边：3 4,权值： 12 加入边：2 7,权值： 14 加入边：2 3,权值： 16 加入边：4 5,权值： 22 加入边：5 6,权值： 25 weight of MST is 99 */ #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int parent[10]; int n,m; int i,j; struct edge{ int u,v,w; //边的顶点，权值 }edges[10]; //初始化并查集 void UFset(){ for(i=1; i<=n; i++) parent[i] = -1; } //查找i的跟 int find(int i){ int temp; //查找位置 for(temp = i; parent[temp] >= 0; temp = parent[temp]); //压缩路径 while(temp != i){ int t = parent[i]; parent[i] = temp; i = t; } return temp; } //合并两个元素a,b void merge(int a,int b){ int r1 = find(a); int r2 = find(b); int tmp = parent[r1] + parent[r2]; //两个集合节点数的和 if(parent[r1] > parent[r2]){ parent[r1] = r2; parent[r2] = tmp; }else{ parent[r2] = r1; parent[r1] = tmp; } } void kruskal(){ int sumWeight = 0; int num = 0; int u,v; UFset(); for(int i=0; i<m; i++) { u = edges[i].u; v = edges[i].v; if(find(u) != find(v)){ //u和v不在一个集合 printf("加入边：%d %d,权值： %d\n", u,v,edges[i].w); sumWeight += edges[i].w; num ++; merge(u, v); //把这两个边加入一个集合。 } } printf("weight of MST is %d \n", sumWeight); } //比较函数，用户排序 int cmp(const void * a, const void * b){ edge * e1 = (edge *)a; edge * e2 = (edge *)b; return e1->w - e2->w; } int main() { scanf("%d %d", &n, &m); for(i=0; i<m; i++){ scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w); } qsort(edges, m, sizeof(edge), cmp); kruskal(); return 0; } /* 测试数据： 7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24 输出： 加入边：1 6,权值： 10 加入边：3 4,权值： 12 加入边：2 7,权值： 14 加入边：2 3,权值： 16 加入边：4 5,权值： 22 加入边：5 6,权值： 25 weight of MST is 99 */
