求最小生成树(Kruskal算法)实验报告

学生实验报告学院：软件与通信工程学院课程名称：离散数学（软件）专业班级：12软件2班姓名：杨滨学号：0123707学生实验报告（2）学生姓名杨滨学号0123707同组人实验项目求最小生成树（Kruskal算法）□必修□选修□演示性实验□验证性实验□操作性实验□综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.12(四)89A节一、实验综述1、实验目的及要求（1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；（2）掌握Prim算法和Kruskal算法的思想及两者之间的区别；（3）编写程序，分别利用Prim算法和Kruskal算法实现，求出最小代价生成树，输出构成最小代价生成树的边集。实验要求：给出如右图的边权图，求最小生成树。认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC++6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#includestdio.h#defineVERTS6structedge{intfrom,to;//起顶点，终顶点intfind,val;//标记,顶点间边长structedge*next;};typedefstructedgenode;node*find_min_cost(node*);voidmin_tree(node*);intv[VERTS+1]={0};//记录顶点即下标，值即出现过的次数voidmain(){intdata[10][3]={{1,0,6},{0,3,5},{3,5,2},{5,4,6},{4,1,3},{2,1,5},{2,0,1},{2,3,5},{2,5,4},{2,4,6}};√√//表示有10条线，例如{1,0,6}表示1和0距离为6node*head,*ptr,*new_node;head=NULL;printf(Addgraph:\n);for(inti=0;i10;i++){for(intj=1;j=VERTS;j++){if(data[i][0]==j){new_node=newnode;new_node-from=data[i][0];new_node-to=data[i][1];new_node-val=data[i][2];new_node-find=0;new_node-next=NULL;if(head==NULL){head=new_node;head-next=NULL;ptr=head;}else{ptr-next=new_node;ptr=ptr-next;}}}}for(ptr=head;ptr!=NULL;ptr=ptr-next)printf(Begin[%d]\tEnd[%d]\t\tPath[%d]\n,ptr-from,ptr-to,ptr-val);printf(\nAddMinTree:\n);min_tree(head);putchar('\n');}voidmin_tree(node*head)//建立最小生成树{node*ptr,*tmptr;intresult=0;//布尔值，是否做出输出结果for(ptr=head;ptr!=NULL;ptr=ptr-next)//遍历十条边{tmptr=find_min_cost(head);//找出最小边顶点v[tmptr-from]++;//当前起点已选自加1次v[tmptr-to]++;//当前终点已选自加1次if(v[tmptr-from]1&&v[tmptr-to]1){/*这个IF语句就是一个防止生成树中有回路；因为v[tmptr-from]与v[tmptr-to]都出现过一次，这棵树的叶子结点都为1，所以当两个结点同时为2时，就形成回路*/v[tmptr-from]--;v[tmptr-to]--;result=1;}elseresult=0;if(result==0)printf(Begin[%d]\tEnd[%d]\t\tPath[%d]\n,tmptr-from,tmptr-to,tmptr-val);}}node*find_min_cost(node*head)//最小边查找{intmin_val=100;node*ptr,*tmptr;for(ptr=head;ptr!=NULL;ptr=ptr-next){if(ptr-valmin_val&&ptr-find==0)//当当前边最小时并当前顶点没有被选择过{min_val=ptr-val;tmptr=ptr;}}//整个循环遍历完毕找到最小连min_valtmptr-find=1;//并标记该顶的边已选择returntmptr;}三、结论1、实验结果2、分析讨论在编写这个程序时，我们先要非常熟悉kruskal算法，kruskal算法总共选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合内。然后根据这个算法用c++实践出来，程序长而又复杂，需要多多联系算法，以后的时间中还得多多练习。四、指导教师评语及成绩：成绩：指导教师签名：批阅日期：