合肥工业最小生成树

《离散数学》实验报告《离散数学》最小生成树问题姓名：学号：班级：实验地点：实验楼四号楼第三机房实验时间：2014-12-3《离散数学》实验报告1实验目的和要求八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？从～到234567811.32.10.90.71.82.01.820.91.81.22.82.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.5目的运用最小生成树思想和求最小生成树程序解决实际问题。2实验环境和工具C++语言环境实验Devec++5编译器3实验过程3.1程序思想1、将各个油井抽象化为图的顶点，它们之间的距离为图的权值2、用邻接矩阵储存图的顶点和权值3、用一个辅助数组储存未选进最小生成树的边和顶点4、主算法prim算法的图解《离散数学》实验报告基本思想假设G=（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中Vi∈U,Vj∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组close[]，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。3.2程序核心代码#includestdio.h#includestring.h#includemalloc.h#includeiostream#includeiomanipusingnamespacestd;#defineMAX10//最多顶点个数266115522网最小生成树413265552211334441365666655553344《离散数学》实验报告#defineINFINIT35768//表示极大值，即∞typedefstruct{doubleadj;//adj是权值类型}ArcNode;typedefstruct{intvexs[MAX],vexnum,arcnum;/*vexs表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ArcNodearcs[MAX][MAX];/*邻接矩阵*/}AdjMatrix;typedefstruct{intadjvex;//存放顶点编号doublelowcost;//存放顶点权值}Node;Nodeclose[MAX];//求最小生成树时的辅助数组//intflag=0;AdjMatrix*creat(AdjMatrix*G)//创建无向网{inti,j;doubleweight;G-vexnum=8;for(i=1;i=G-vexnum;i++)G-vexs[i]=i;for(i=1;i=G-vexnum;i++){for(j=i+1;j=G-vexnum;j++){cout请输油井i到油井j距离：;cinweight;G-arcs[i][j].adj=weight;G-arcs[j][i].adj=weight;《离散数学》实验报告}}return(G);}intMinium(AdjMatrix*G,Nodeclose[])//close[]中权值最小的边{inti,k;doublemin;min=INFINIT;//置最小权值为INFINITfor(i=1;i=G-vexnum;i++)if(close[i].lowcostmin&&close[i].lowcost!=0){min=close[i].lowcost;k=i;}returnk;//返回权值最小的边在辅助数组中的位置}voidprim(AdjMatrix*G,intu)//普里姆算法//从顶点u出发,按普里姆算法构造连通网G的最小生成树，并输出生成树的每条边{inti,j,k,k0,u0,v0,n=0;doubles=0;AdjMatrix*p;p=(AdjMatrix*)malloc(sizeof(AdjMatrix));k=u;p-vexs[n++]=u;close[k].lowcost=0;//初始化U={u}for(i=1;i=G-vexnum;i++)《离散数学》实验报告if(i!=k){//对V-U中的顶点i,初始化close[i]close[i].adjvex=u;close[i].lowcost=G-arcs[k][i].adj;}/*close[i]是指未选中的边*/for(j=1;j=G-vexnum-1;j++){//找n-1条边(n=G-vexnum)k0=Minium(G,close);//close[k0]中存有当前最小边(u0,v0)的信息u0=close[k0].adjvex;//u0∈Uv0=G-vexs[k0];//v0∈V-Up-vexs[n++]=v0;//将终点放入数组中s+=close[k0].lowcost;//求最小生成树的权值之和cout(u0-v0)\tclose[k0].lowcostendl;//输出最小生成树的路径close[k0].lowcost=0;//将顶点v0纳入U集合for(i=1;i=G-vexnum;i++)//在顶点v0并入U之后,更新closedge[i]if(G-arcs[k0][i].adjclose[i].lowcost){close[i].lowcost=G-arcs[k0][i].adj;close[i].adjvex=v0;}}cout\n最小生成树中的顶点序列为：{;for(i=0;iG-vexnum;i++)coutp-vexs[i];cout}endl;cout\n最小生成树的权值之和为：sendl;}intmain()//主函数{intst;AdjMatrix*G,*p;《离散数学》实验报告p=(AdjMatrix*)malloc(sizeof(AdjMatrix));cout***********************计算机科学与技术13-1裴现坤**************************endl;coutsetw(46)普里姆最小生成树算法!endl;cout\n********************************************************************************endl;G=creat(p);st=1;coutendl----------------利用普里姆算法从起点1号油井出发,最小生成树的路径如下-------endlendl;cout\n*****************************************************endl;cout(起点-终点)权值endlendl;prim(G,st);system(PAUSE);return1;}3.1输入结果《离散数学》实验报告3.1运行结果3.2运行结果分析根据最小生成树路径可以得出所需要的最短油管是10.2km，连接方式是按照1-5-4-8-7-6-3-2的序列他们之间的距离是5+0.7+0.7+0.8+0.5+0.6+1+0.9=10.2km《离散数学》实验报告4实验心得1、通过对油井的分析，了解最小生成树算法prim算法的实际意义。2、通过上机加查找资料，自学使自己的程序功底得到很大的提升，能够讲算法演化成真正的程序了。3、通过对离散数学的学习，知道了科学的现实意义，更加加深了我对计算机专业的兴趣，使自己相信通过自己的努力，一定会成为个出色的软件工程师