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

学 生 实 验 报 告 学 院： 软件与通信工程学院 课程名称： 离散数学（软件） 专业班级： 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 #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 v[VERTS+1]={0}; //记录顶点即下标，值即出现过的次数 void main() { int data[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距离为6 node *head,*ptr,*new_node; head=NULL; printf(Add graph:\n); for (int i=0; i10; i++) { for (int j=1; j=VERTS; j++) { if (data[i][0]==j) { new_node=new node; 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(\nAdd Min Tree:\n); min_tree(head)