实验五最小生成树

《实验五最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、韶关学院学生实验报告册实验课程名称：数据结构与算法实验项目名称：实验五最小生成树实验类型（打"）:（基础、综合、设计丿系:计算机科学学院专业：计算机科学技术号:姓名：***指导老师：陈正铭韶关学院教务处编制一、实验预习报告内容预习日期：2011年9月18日【实验目的】（1）复习图的存储方法和图的遍历方法。（2）进一步掌握图的非线性特点、递归特点和动态特性。（3）掌握最小生成树的求解算法。【实验内容】（1）用Prim算法求最小生成树。（2）输入网的二维矩阵，输出最小生成树。【实验要求】（1）利用C或C++语言完成算法设计和程序设计。（2）上机调试通过

2、实验程序。（3）输入数据，并求最小生成树。（4）给出具体的算法分析，包括时间复杂度和空间复杂度等。（5）撰写实验报告。【软件平台】Windows2000,VisualC++6.0【程序组成】由一个main（）主函数（完成数据输入和函数调用）、三个功能函数：prim（）〃求最小生成树的prim算法adjg（）〃建立无向图prg（）〃输11!无向图的邻接矩阵构成如下图所示:【设计思想】图采用邻接矩阵存储结构，设数组closest[i]存储刚访问的距离顶点v最近的顶点，全局变量g二维数组用于存储最小生成树边的信息。假设G=（V,E）为一连通网，顶点集V二

3、｛vl,v2,…,vn）,E为网中所有带权边的集合。设置两个新的集合U和T,其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={vl}（假设构造最小生成树时，从顶点vl出发），集合T的初值为T={}。从所有uWU,vEV-U的边中,选取具有最小权值的边（u，v）,将顶点v加入集合U中，将边（u,V）加入集合T中，如此不断重复，直到U=V时，最小生成树构造完毕，这时集合T屮包含了最小生成树的所有边。【疑问】怎么实现最小生成树求解的Kruskal算法？（这部分内容因人而异，也可不写）实验预习评分:二.实验原始

4、（数据）记录实验时间：2011年9月21日（星期三第7,8节）实验同组人:-Inlxi【程序运行结果】C我的工作文件'教案与课件、数齬结构本人电子教案10计算机'实.・7•?〈•?〈•?〈•?〈•?〈•?〈•7〈??????-5即，，，，，，，巨那点点点点点点点黑2鬼己己己己己己己衣走走走走走走走刑JhtJAA.1■A.1■A.1■A.1■A.1■A.1■A.1■」%l7吃边边边边边边边.酗己八123456?F顶^WWW无JAJAJAJAJAJAJAJAJA012345：1,3,10=1,4,11：2,3,3：2,5,13=3,4,4：4,5

5、,?411co4co75co13co7co通过分析输入数据和运行结果，证明程序顺利完成实验内容和要求。指导教师批阅及签名签名:三.实验报告内容2011年9月21日【实验程序主要代码】:#defineinf9999#defineMAXLEN40voidprim(intg[][MAXLEN],intn){intlowcost[MAXLEN],closest[MAXI.EN];inti,j,k,min;for(i=2;i<=n;i++){lowcost[i]=g[l][i];closest[i]=l;}lowcost[l]=0;for(i=2;i<=n;

6、i++){min二inf;k二0;//prim的函数//n个顶点，nT条边//初始化//顶点未加入到最小生成树中//标志顶点1加入U集合//形成n-l条边的生成树for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]

7、[j]=g[k][j];closest[j]=k;}printf("");//顶点k加入U//修改rh顶点k到其他顶点边的权值intadjg(intg[][MAXLEN]){intn,e,i,j,k,vl,v2,weight;printf("输入顶点个数，边的条数:scanf("%d,%d",&n,&e);for(i=l;i〈二n;i++)for(j=l;j<=n;j++)g[i][j]二inf;//建立无向图〃）；//初始化矩阵，全部元素设为无穷大for(k=l;k〈=e;k++){printfC输入第％d条边的起点，终点，权值:〃,k);s

8、canf(^d,%d,%d",&vl,&v2,&weight);g[vl][v2]=weight;g[v2][vl]=we