求最小生成树(Kruskal算法)实验报告(共6页).doc
精选优质文档-倾情为你奉上学 生 实 验 报 告 学 院： 软件与通信工程学院 课程名称： 离散数学（软件） 专业班级： 12软件2班 姓 名： 杨滨 学 号： 专心-专注-专业学生实验报告（2）学生姓名杨滨学号同组人实验项目求最小生成树（Kruskal算法）必修 选修演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.12(四) 89A节一、实验综述1、实验目的及要求（1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；（2）掌握Prim算法和Kruskal算法的思想及两者之间的区别；（3）编写程序，分别利用Prim算法和Kruskal算法实现，求出最小代价生成树，输出构成最小代价生成树的边集。实验要求：给出如右图的边权图，求最小生成树。认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件 计算机、VC+6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#include<stdio.h> #define VERTS 6 struct edge int from,to; /起顶点，终顶点 int find,val; /标记,顶点间边长 struct edge *next; ; typedef struct edge node; node *find_min_cost(node *); void min_tree(node *); int vVERTS+1=0; /记录顶点即下标，值即出现过的次数 void main() int data103=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("Add graph:n"); for (int i=0; i<10; i+) for (int j=1; j<=VERTS; j+) if (datai0=j) new_node=new node; new_node->from=datai0; new_node->to=datai1; new_node->val=datai2; 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%dtEnd%dttPath%dn",ptr->from,ptr->to,ptr->val); printf("nAdd Min Tree:n"); min_tree(head); putchar('n'); void min_tree(node *head) /建立最小生成树 node *ptr,*tmptr; int result=0; /布尔值，是否做出输出结果 for (ptr=head; ptr!=NULL; ptr=ptr->next) /遍历十条边 tmptr=find_min_cost(head); /找出最小边顶点 vtmptr->from+; /当前起点已选自加1次 vtmptr->to+; /当前终点已选自加1次 if (vtmptr->from>1 && vtmptr->to>1) /*这个IF语句就是一个防止生成树中有回路；因为vtmptr->from与vtmptr->to都出现过一次，这棵树的叶子结点都为1，所以当两个结点同时为2时，就形成回路*/ vtmptr->from-; vtmptr->to-; result=1; else result=0; if (result=0) printf("Begin%dtEnd%dttPath%dn",tmptr->from,tmptr->to,tmptr->val); node *find_min_cost(node *head) /最小边查找 int min_val=100; node *ptr,*tmptr; for (ptr=head;ptr!=NULL;ptr=ptr->next) if (ptr->val<min_val && ptr->find=0) /当当前边最小时并当前顶点没有被选择过 min_val=ptr->val; tmptr=ptr; /整个循环遍历完毕找到最小连min_val tmptr->find=1; /并标记该顶的边已选择 return tmptr; 三、结论1、实验结果2、分析讨论在编写这个程序时，我们先要非常熟悉kruskal算法，kruskal总共选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生的具有最小耗费的边加入已选择的边的集合内。然后根据这个算法用c+实践出来，程序长而又复杂，需要多多联系算法，以后的时间中还得多多练习。四、指导教师评语及成绩：成绩： 指导教师签名： 批阅日期：
