克鲁斯卡尔算法实验报告

第1页实验报告实验原理：Kruskal算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。如教材153页的图4.21(a)所示，按照Kruskal方法构造最小生成树的过程如图4.21所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n－1条边，故反复上述过程，直到选取了n－1条边为止，就构成了一棵最小生成树。实验目的：本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal算法。通过练习，加强对算法的理解，提高编程能力。实验内容：（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。实验器材（设备、元器件）：PC机一台，装有C语言集成开发环境。数据结构与程序：#includeiostream#includecstdio#includealgorithmusingnamespacestd;第2页#defineX105typedefstructEdge{intw;intx,y;}Edge;//储存边的struct，并储存边两端的结点classGraphNode{public:intdata;intfather;intchild;}GraphNode[X];//储存点信息的并查集类（点的值，父结点，子结点）Edgeedge[X*X];boolcomp(constEdge,constEdge);voidupdate(int);intmain(){intnode_num;intsum_weight=0;FILE*in=fopen(C:\\Users\\瑞奇\\Desktop\\编程实验\\数据结构实验\\FileTemp\\in.txt,r);coutReadingdatafromfile...endlendl;//coutPleaseinputthetotalamountofnodesinthisGraph:;//cinnode_num;fscanf(in,%d,&node_num);//coutPleaseinputthedataofeachnode:endl;for(inti=1;i=node_num;i++){//cinGraphNode[i].data;fscanf(in,%d,&GraphNode[i].data);GraphNode[i].father=GraphNode[i].child=i;}//初始化点集//coutPleaseinputtherelationbetweennodesinthisformatandendwith(000):endl(first_nodesecond_nodeegde_weight)endl;intx,y,w,tmp_cnt=1;//while(cinxyw&&w)while(fscanf(in,%d%d%d,&x,&y,&w)!=EOF&&w)edge[tmp_cnt].w=w,edge[tmp_cnt].x=x,edge[tmp_cnt++].y=y;fclose(in);sort(edge+1,edge+tmp_cnt,comp);//对边权进行排序coutTheMinSpanTreecontainsfollowingedges:endlendl;for(inti=1;i=tmp_cnt;i++)//循环找最小边if(GraphNode[edge[i].x].father!=GraphNode[edge[i].y].father)第3页{intn=edge[i].x;intm=n;if(GraphNode[m].father!=m)//使用并查集对边是否可用进行判断{m=GraphNode[m].father;GraphNode[m].father=GraphNode[edge[i].y].father;}GraphNode[edge[i].x].father=GraphNode[edge[i].y].father;GraphNode[edge[i].y].child=GraphNode[edge[i].x].child;while(GraphNode[n].child!=n)n=GraphNode[n].child;update(n);//在合并点集后对并查集进行更新sum_weight+=edge[i].w;//计算总权cout\tTheedgebetweenGraphNode[edge[i].x].data&GraphNode[edge[i].y].datawiththeweightedge[i].wendl;}coutendlAndthetotalweightoftheMinSpanTreeaddupto:sum_weightendl;return0;}boolcomp(constEdgea,constEdgeb){returna.wb.w;}voidupdate(intn){if(GraphNode[n].father==n)return;GraphNode[GraphNode[n].father].child=GraphNode[n].child;//更新孩子结点update(GraphNode[n].father);//递归更新GraphNode[n].father=GraphNode[GraphNode[n].father].father;//更新父结点}程序运行结果：运行程序，程序读取文件，获取文件中关于图的信息：结点数，结点值，结点间边权。然后使用Kruskal算法对录入信息进行处理：1.对边权排序第4页2.取最小权边，若边的端结点不在同一集合众，则使边的端结点加入集合并删除该边；若边的端结点本来就在同一集合中，直接删除该边3.循环执行步骤2，直到集合中包含所有结点和结点数-1条边输入为：6123456126131145235253345356364462566程序运行结果如下图：实验结论：第5页Kruskal算法其实是一种贪心算法，每次选取符合条件的边，加入边集（此程序中直接输出）。直到所有结点和最少边全部包含在同一集合中，算法结束。总结及心得体会：在使用并查集的时候，注意在合并集合后要更新并查集的父结点和子结点。其实Kruskal算法的复杂度为O(E^2)，其复杂度和边条数有关，和结点数无关，所以适用于稀疏图。