资源描述：
《求最小生成树(Kruskal算法)实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、学生实验报告学院：软件与通信工程学院课程名称：离散数学（软件）专业班级：12软件2班姓名：杨滨学号：学生实验报告（2）学生姓名杨滨学号同组人实验项目求最小生成树（Kruskal算法）√□必修□选修√□演示性实验□验证性实验□操作性实验□综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.12(四)89A节一、实验综述1、实验目的及要求（1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；（2）掌握Prim算法和Kruskal算法的思想及两者之间的区别；（3）编写程序，分别利用Prim算法和Kruskal算法实
2、现，求出最小代价生成树，输出构成最小代价生成树的边集。实验要求：给出如右图的边权图，求最小生成树。认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC++6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#include#defineVERTS6structedge{intfrom,to;//起顶点，终顶点intfind,val;//标记,顶点间边长structedge*next;};typedefstructedgenode;n
3、ode*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:");for(inti=0;i<1
4、0;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
5、;ptr!=NULL;ptr=ptr->next)printf("Begin[%d]tEnd[%d]ttPath[%d]",ptr->from,ptr->to,ptr->val);printf("AddMinTree:");min_tree(head);putchar('');}voidmin_tree(node*head)//建立最小生成树{node*ptr,*tmptr;intresult=0;//布尔值，是否做出输出结果for(ptr=head;ptr!=NULL;ptr=ptr->next)//遍历十条边{tmptr=find_min_co
6、st(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]t
7、End[%d]ttPath[%d]",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->valfind==0)//当当前边最小时并当前顶点没有被选择过{min_val=ptr->val;tmptr=ptr;}}//整个循环遍历完毕找到最小连min_valt
