最小生成树-实验报告

FpgFpg实验五最小生成树一、需求分析1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。2、测试数据见下程序。二、概要设计主程序：intmain(){初始化；while(条件){接受命令;处理命令;}return0;}三、详细设计#includeiostream//头文件usingnamespacestd;#defineMAX_VERTEX_NUM20//最大结点数#defineMAX200typedefstructClose//结构体FpgFpg{charadjvex;intlowcost;}Close,close[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;ArcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListverties;intvexnum,arcnum;}ALGraph;ALGraphG;//对象GintLocateVek(ALGraph,char);//返回结点位置intminimum(close);//返回最小数voidMinSpanTree_PRIM(ALGraph,char);//最小生成树voidCreate(ALGraph&);//创建邻接表intmain(){chara;inti=1;Create(G);/*for(inti=1;i=G.vexnum;i++){for(s=G.verties[i].firstarc;s!=NULL;s=s-nextarc)coutG.verties[i].data---G.verties[s-adjvex].data====s-infoendl;}*/while(i){cout输入起点:;cina;MinSpanTree_PRIM(G,a);cout如果结束输入'0',否则输入'1':;cini;}return0;}FpgFpgintLocateVek(ALGraphG,charu){inti;for(i=1;i=G.vexnum;i++)if(u==G.verties[i].data)returni;return-1;}intminimum(closem)//返回最小数{inti=0,j,n=200;for(i=1;i=G.vexnum;i++)if(m[i].lowcostn&&m[i].lowcost!=0){n=m[i].lowcost;j=i;}returnj;}voidMinSpanTree_PRIM(ALGraphG,charu){intj,k,a;closeclosedge;ArcNode*s,*p,*q;for(j=1;j=MAX_VERTEX_NUM;j++)closedge[j].lowcost=MAX;//把所有值都赋为最大k=LocateVek(G,u);for(j=1;j=G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;for(s=G.verties[k].firstarc;s!=NULL;s=s-nextarc)if(j==s-adjvex){closedge[j].lowcost=s-info;break;}}closedge[k].lowcost=0;cout最小生成树:{;//查找并输出最小生成树for(j=1;jG.vexnum;j++){k=minimum(closedge);cout(closedge[k].adjvex,G.verties[k].data);closedge[k].lowcost=0;FpgFpgfor(inti=1;i=G.vexnum;i++){for(p=G.verties[k].firstarc;p!=NULL;p=p-nextarc)if(p-infoclosedge[i].lowcost&&i==p-adjvex){closedge[i].adjvex=G.verties[k].data;closedge[i].lowcost=p-info;}}}cout}endl;cout边及对应权值:endl;//输出边及对应权值for(j=G.vexnum;j=1;j--){if(closedge[j].lowcost==0&&G.verties[j].data!=u){cout(closedge[j].adjvex,G.verties[j].data)==;a=closedge[j].adjvex;for(q=G.verties[j].firstarc;q!=NULL;q=q-nextarc)if(a-64==q-adjvex)coutq-infoendl;}}}voidCreate(ALGraph&G){inti,j,k,x;chara,b;ArcNode*s;cout输入顶点数(1-20):;cinG.vexnum;cout输入边数:;cinG.arcnum;cout输入顶点信息:endl;for(i=1;i=G.vexnum;i++){cinG.verties[i].data;G.verties[i].firstarc=NULL;}for(i=1;i=G.arcnum;i++){cout输入相邻两结点和权值;cinab;cinx;j=a-64;k=b-64;//将字符型转化成整数型s=newArcNode;FpgFpgs-info=x;s-adjvex=k;s-nextarc=G.verties[j].firstarc;G.verties[j].firstarc=s;s=newArcNode;s-info=x;s-adjvex=j;s-nextarc=G.verties[k].firstarc;G.verties[k].firstarc=s;}}四、调试分析1、在写程序时遇到很多有关专业名词のC语言编译，没有完全套用书上の固有解释，而是按照自己有限の英语词汇の理解去编译の。2、通过求最小生成树，进一步掌握了图の含义。五、运行结果FpgFpg六、实验环境（1）WindowsXP系统下（2）编程环境：VC6.0++，TC2.0七、实验体会通过此实验，通过求最小生成树，进一步掌握了图の含义。知道了普里姆算法。通过本次课程设计，锻炼了我们の实际操作能力，培养了我们严密の思维和严谨の态度。