求最小生成树Kruskal算法实验报告.doc
《求最小生成树Kruskal算法实验报告.doc》由会员分享，可在线阅读，更多相关《求最小生成树Kruskal算法实验报告.doc（5页珍藏版）》请在冰点文库上搜索。
学生实验报告
学院：
软件与通信工程学院
课程名称：
离散数学（软件）
专业班级：
12软件2班
姓名：
杨滨
学号：
0123707
学生实验报告
（2）
学生姓名
杨滨
学号
0123707
同组人
实验项目
求最小生成树（Kruskal算法）
√
□必修□选修
√
□演示性实验□验证性实验□操作性实验□综合性实验
实验地点
W101
实验仪器台号
指导教师
赵晓平
实验日期及节次
2013.12.12（四）89A节
一、实验综述
1、实验目的及要求
（1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法；
（2）掌握Prim算法和Kruskal算法的思想及两者之间的区别；
（3）编写程序，分别利用Prim算法和Kruskal算法实现，求出最小代价生成树，输出构成最小代价生成树的边集。
实验要求：
给出如右图的边权图，求最小生成树。
认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。
2、实验仪器、设备或软件
计算机、VC++6.0、office、相关的操作系统等。
二、实验过程（实验步骤、记录、数据、分析）
#include
#defineVERTS6
structedge{
intfrom,to;//起顶点，终顶点
intfind,val;//标记,顶点间边长
structedge*next;};
typedefstructedgenode;
node*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距离为6
node*head,*ptr,*new_node;
head=NULL;
printf（"Addgraph:
\n"）;
for（inti=0;i<10;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;ptr!
=NULL;ptr=ptr->next）
printf（"Begin[%d]\tEnd[%d]\t\tPath[%d]\n",ptr->from,ptr->to,ptr->val）;
printf（"\nAddMinTree:
\n"）;
min_tree（head）;
putchar（'\n'）;
}
voidmin_tree（node*head）//建立最小生成树
{
node*ptr,*tmptr;
intresult=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;
}
elseresult=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）//最小边查找
{
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_val
tmptr->find=1;//并标记该顶的边已选择
returntmptr;
}
三、结论
1、实验结果
2、分析讨论
在编写这个程序时，我们先要非常熟悉kruskal算法，kruskal算法总共选择n-1条边，所使用的贪婪准则是：
从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合内。
然后根据这个算法用c++实践出来，程序长而又复杂，需要多多联系算法，以后的时间中还得多多练习。
四、指导教师评语及成绩：
成绩：
指导教师签名：
批阅日期：
升级会员 