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

1、精选优质文档-倾情为你奉上学 生 实 验 报 告 学 院： 软件与通信工程学院 课程名称： 离散数学（软件） 专业班级： 12软件2班 姓 名： 杨滨 学 号： 专心-专注-专业学生实验报告（2）学生姓名杨滨学号同组人实验项目求最小生成树（Kruskal算法）必修 选修演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.12(四) 89A节一、实验综述1、实验目的及要求（1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；（2）掌握Prim算法和Kruskal算法的思想及两者之间的区别；（3）编写

2、程序，分别利用Prim算法和Kruskal算法实现，求出最小代价生成树，输出构成最小代价生成树的边集。实验要求：给出如右图的边权图，求最小生成树。认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件 计算机、VC+6.0、office、相关的操作系统等。二、实验过程（实验步骤、记录、数据、分析）#include<stdio.h> #define VERTS 6 struct edge int from,to; /起顶点，终顶点 int find,val; /标记,顶点间边长 struct edge *n

3、ext; ; 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");

4、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; p

5、tr=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

6、 (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-&g

7、t;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条边，