裴现坤最小生成树讲解

1、离散数学最小生成树问题名：裴现坤姓学2013211613 号 ：13-1： 班级班计算机科学与技术:验地实点实验楼四号楼第三机房 :验时实间2014-12-3离散数学实验报告1实验目的和要求八口海上油井相互间距离如下表，其中 1号井离海岸最近，为5km。问从海 岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管 只准在油井处分叉）？从23456782 1.2 0.9 2.8 1.8 2.31.0 3 1.7 2.5 1.9 2.60.9 1.6 0.7 4 1.50.80.9 5 1.11.0 6 0.60.57目的运用最小生成树思想和求最小生成树程序解决实际问题2实验环境

2、和工具C+语言环境实验Deve c+ 5编译器3实验过程3.1程序思想1、将各个油井抽象化为图的顶点，它们之间的距离为图的权值2、用邻接矩阵储存图的顶点和权值3、用一个辅助数组储存未选进最小生成树的边和顶点4、主算法prim算法的图解1 16 55 114 254253 33 4 224 3 6656 56最小生成树网基本思想假设G = （V,巳是一个具有n个顶点的连通网，T=（U,TE）是G的最小生 成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开 始时，首先从V中任取一个顶点（假定取 V），将它并入U中，此时oU=V，然 后只要U是V的真子集，就从那些其一个端点已在

3、 T中，另一个0端点仍在T外 的所有边中，找一条最短（即权值最小）边，假定为（i,j ），其中V U,V （V-U）, 并把该边（i,j ）和顶点j分别并入T的边集TE和顶ji点集U,如此进行下去， 每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入 到生成树T的顶点集中，此时U=V TE中含有n-1条边，T就是最后得到的最小 生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法” o为了实现这个算法在本设计中需要设置一个辅助数组close，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的 边时，此时最小生成树的形态就不

4、唯一，此时可以在程序中采用递归的算法思想 求出每个最小生成树。3.2程序核心代码#i ncludestdio.h#i ncludestri ng.h#i ncludemalloc.h#i ncludeiostream#i nclude ioma nip using n amespace std;最多顶点个数 #define MAX 10离散数学实验报告#defi ne INFINIT 35768 表示极大值，即 typedef structdouble adj;/adj 是权值类型ArcNode;typedef structint vexsMAX,vex nu m,arc num;/*vexs

5、表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ArcNode arcsMAXMAX;/* 邻接矩阵 */AdjMatrix;typedef structint adjvex;/存放顶点编号double lowcost;/存放顶点权值Node;Node closeMAX;/求最小生成树时的辅助数组/int flag=0;AdjMatrix *creat(AdjMatrix *G) / 创建无向网int i,j;double weight;G-vex num = 8;for(i=1;ivex nu m;i+)G-vexsi=i;for(i=1;ivex nu m;i+)fo

6、r(j=i+1;jvex nu m;j+)潣瑵?请输油井？椼?到油井？樼?距离：；cin weight;G-arcsij.adj=weight;G-arcsji.adj=weight;离散数学实验报告return(G);intMinium(AdjMatrix *G,Node close)/close中权值最小的边int i,k;double mi n;min=INFINIT; 置最小权值为 INFINITfor(i=1;ivex nu m;i+)if(closei .Io wcostvmi n&closei .Io wcost!=0) mi n=closei.lowcost;k=i;retur

7、n k;返回权值最小的边在辅助数组中的位置prim(AdjMatrix *Gvoid ,int u)普里姆算法并输出生成树的每条的最小生成 树，u出发按普里姆算法构造连通网G/从顶点边int i,j,k,k0,u0,v0, n=0;double s=0;AdjMatrix *p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);k=u;p-vexs n+=u;closek.lowcost=0;/初始化 U=u for(i=1;ivex nu m;i+)离散数学实验报告if(i!=k)对V-U中的顶点i,初始化closeiclosei.adjvex=u;closei

8、.lowcost=G-arcski.adj;/* closei是指未选中的边*/for(j=1;jvexnum-1;j+)找 n-1 条边(n=G-vexnum)k0=Minium(G,close);/closek0中存有当前最小边 (u0, v0)的信息 u0=closek0.adjvex;/u0 Uv0=G-vexsk0;/v0 V-Up-vexs n+=v0;将终点放入数组中 s+=closek0.lowcost;求最小生成树的权值之和 cout(vvu0vv-xvv0v)vv closek0.lowcostendl;输出最小生成树的路径closek0.lowcost=0;将顶点 v0

9、纳入 U 集合for(i=1;ivexnum;i+)/ 在顶点 v0 并入 U 之后，更新 closedgei if(G-arcsk0i.adjarcsk0i.adj;closei.adjvex=v0;coutvexsiv ;for(i=0;ivex nu m;i+) coutcoutvve ndl;se ndl; cout最小生成树的权值之和为：主函数 / int mai n() int st;,*p; AdjMatrix *G离散数学实验报告p=(AdjMatrix *)malloc(sizeof(AdjMatrix);coutvv*计算机科学与技术 13-1裴现坤*e nd, 潣瑵？敳暉?普里姆最小生成树算法!endl;cout*e ndrG=creat(p); st=1;coutvvendlvv利用普里姆算法从起点1号油井出发,最小生成树的路径如下e ndle ndl;coute ndl;*cout 终点)权值 5 4 ? C7-fc C8-3 C3-23.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离散数学实