求最小生成树实验报告.docx

紡財俺乂曙学生实验报告软件与通信工程学院12软件2班学 院 课程名称 专业班级 名 学 号学生实验报告（2）学生姓名杨滨 学号 0123707同组人实验项目求最小生成树（Kruskal算法）□必修 □选修 □演示性实验□验证性实验 □操作性实验 □综合性实验实验地点W101实验仪器台号指导教师赵晓平实验日期及节次2013.12.12(四)89A 节一、实验综述1、实验目的及要求（1） 了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用 贪心策略设计算法；（2） 掌握Prim算法和Kruskal算法的思想及两者之间的区别；（3） 编写程序，分别利用Prim算法和Kruskal算法实现，求出最小代价生成05635522665树，输出构成最小代价生成树的边集 实验要求：给出如右图的边权图，求最小生成树认真完成实验题，能正确运行，提交实验报告并上 传程序，实验报告要求写出操作步骤、结果、问题、解 决方法、体会等2、实验仪器、设备或软件计算机、VC++6.0、office、相关的操作系统等二实验过程（实验步骤、记录、据、分析）#include#define VERTS 6struct 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+l]={0}; 〃记录顶点即下标，值即出现过的次数 void main() {int data[10][3]={{l,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 (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);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); //找出最小边顶点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;}else result=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) //最小边查找{int min_val=100;node *ptr,*tmptr;for (ptr=head;ptr!=NULL;ptr=ptr->next){if (ptr->valfind==0) //当当前边最小时并当前顶点没有被选择过{min_val=ptr->val; tmptr=ptr;}} //整个循环遍历完毕找到最小连 min_valtmptr->find=1; //并标记该顶的边已选择return tmptr;三、结论1、实验结果賦 *C:\Docu>ent;m and Settings\Ad>inistrator\J^面建文杵夹\Debug\CpplSl-eze* [ |—Add graph:Begin[1]End[0]PathCfi]Begin[3]End[53Path[2JFn(ir41PathrfilBegin[4]Endtl]PathL3]Wf?ginr5!lEnin 1Pflthrs 1Begin[2]End[0]PathtllBegin[23EndC2]PathCS ]Begin[2]End[5]PathC4]EndC4]PathCS]rldd Min Tree：Begin[2]End[0]PathtllBegin CG ]EndCS]rAL]t[2]Begin[41EndCl]Path[3JPress ■any l;ey to comt inue2、分析讨论在编写这个程序时，我们先要非常熟悉kruskal算法，kruskal算法总共选择n-1条边，所使 用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的 集合内。

然后根据这个算法用C++实践出来，程序长而又复杂，需要多多联系算法，以后的时 间中还得多多练习指导教师评语及成绩：成绩:指导教师签名: 批阅日期：。