离散数学上机最小生成树.doc

**大学集合论与图论上机实验报告课程名称:集合论与图论年级:2014上机实验成绩:指导教师:姓名 上机实验名称:最小生成树学号:3120140901109上机实验日期:2015-11-15上机实验编号:组号:上机实验时间:两课时   一、实验目的掌握图的存储表示和以及图的最小生成树算法。2、,并且读入图的内容。 2. 利用克鲁斯卡尔算法求网络的最小生成树。 3. 实现构造生成树过程中的连通分量抽象数据类型。 4. 以文本形式输出对应图的最小生成树各条边及权值。3、使用环境Windows7vs2012四、核心代码及调试过程#include<iostream>usingnamespacestd;#defineMAX_VERTEX_NUM20#defineMAX 200typedefstructClose{charadjvex;intlowcost;}Close,close[MAX_VERTEX_NUM];ode{intadjvex;ode*nextarc;intinfo;}ode;typedefstructVNode{chardata;ode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListverties;intvexnum,um;}ALGraph;ALGraphG;//对象GintLocateVek(ALGraph,char);intminimum(close);voidMinSpanTree_PRIM(ALGraph,char);voidCreate(ALGraph&);intmain(){chara;inti=1;Create(G);/*for(inti=1;i<=;i++){for(s=[i].firstarc;s!=NULL;s=s->nextarc)cout<<[i].data<<"---"<<[s->adjvex].data<<"===="<<s->info<<endl;}*/while(i){cout<<"输入起点:";cin>>a;MinSpanTree_PRIM(G,a);cout<<"如果结束输入'0',否则输入'1':";cin>>i;}return0;}intLocateVek(ALGraphG,charu){inti;for(i=1;i<=;i++)if(u==[i].data)returni;return-1;}intminimum(closem){inti=0,j,n=200;for(i=1;i<=;i++)if(m[i].lowcost<n&&m[i].lowcost!=0){n=m[i].lowcost;j=i;}returnj;}voidMinSpanTree_PRIM(ALGraphG,charu){intj,k,a;closeclosedge;ode*s,*p,*q;for(j=1;j<=MAX_VERTEX_NUM;j++)closedge[j].lowcost=MAX;k=LocateVek(G,u);for(j=1;j<=;j++)if(j!=k){closedge[j].adjvex=u;for(s=[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;j<;j++){k=minimum(closedge);cout<<"("<<closedge[k].adjvex<<","<<[k].data<<")";closedge[k].lowcost=0;for(inti=1;i<=;i++){for(p=[k].firstarc;p!=NULL;p=p->nextarc)if(p->info<closedge[i].lowcost&&i==p->adjvex){closedge[i].adjvex=[k].data;closedge[i].lowcost=p->info;}}}cout<<"}"<<endl;cout<<"边及对应权值:"<<endl;for(j=;j>=1;j--){if(closedge[j].lowcost==0&&[j].data!=u){  cout<<"("<<closedge