最小生成树及其算法

最小生成树及其算法A《离散数学》大作业论文题目：最小生成树及其算法院系：电子工程学院专业：智能科学与技术学号：姓名：二零一一年十一月最小生成树及其算法I摘要连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。本文主要介绍Prim（普里姆）算法及利用。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键字：prum算法最小生成树算法比较最小生成树及其算法11.有关最小生成树的概念最小生成树：连通加权图里权和最小的生成树称为最小生成树。从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：G=(V,E)V={iV|jVVertexType}E={iV,jV|iV,jV∈V∧P(iV,jV)}其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描述顶点类型，集合E中P(iV,jV)的含义是：对有向图来说用“”表示，对无向图来说用“（）”表示，即从iV到jV两个顶点之间存在边。定义二（树）：树包含n（n=0）个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：1）有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。2）除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。3）D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n=0）个子结点。图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，用来存放顶点的信息和边或弧的信息。定义三（邻接矩阵（AdjacencyMatrix））：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）最小生成树及其算法2（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。定义四（生成树）：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。2.prim算法介绍从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。1.输入：一个加权连通图，其中顶点集合为V，边集合为E；2.初始化：Vnew={x}，其中x为集合V中的任一节点（起始点），Enew={}；3.重复下列操作，直到Vnew=V：1.在集合E中选取权值最小的边（u,v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；2.将v加入集合Vnew中，将（u,v）加入集合Enew中；4.输出：使用集合Vnew和Enew来描述所得到的最小生成树。3.prim算法的实现#includestdio.h#defineTURE999typedefstructArcNode{charvexs[10];intedgs[10][10];intn,e;}MGraph;structedg{intv1;intv2;intcost;}A[10],B[10];//创建图最小生成树及其算法3voidGreateMGraph(MGraph*G){inti,j,k,weight,m,n;intch1,ch2;chara,b;printf(\n\t\t输入顶点数边数(格式如:34):);scanf(%d%d,&(G-n),&(G-e));//输入顶点数,边数for(i=0;iG-n;i++){getchar();printf(\n\t\t请输入第%d个顶点:,i+1);scanf(%c,&(G-vexs[i]));//输入顶点}for(i=0;iG-n;i++)for(j=0;jG-n;j++)G-edgs[i][j]=0;for(k=0;kG-e;k++){//getchar();printf(\n\t\t请输入第%d条边的顶点权值(格式如:ij):,k+1);getchar();scanf(%c%c%d,&a,&b,&weight);//scanf(%c,&a);//getchar();//scanf(%c,&b);m=0;n=0;for(m=0;G-vexs[m]!=a;m++);for(n=0;G-vexs[n]!=b;n++);//printf(\n\t\t请输入权值:);scanf(%d,&weight);ch1=m;ch2=n;G-edgs[ch1][ch2]=weight;G-edgs[ch2][ch1]=weight;}}voidprim(MGraph*G,intv){最小生成树及其算法4inti,j,k,min;struct{intadjvex;intlowcost;}closedge[10];for(i=0;iG-n;i++)//初始化{closedge[i].lowcost=G-edgs[v][i];closedge[i].adjvex=v;}closedge[v].lowcost=TURE;for(i=1;iG-n;i++){min=100;/*100为允许的最大权值*/for(j=0;jG-n;j++)if(closedge[j].lowcost!=TURE&&closedge[j].lowcost!=0){if(closedge[j].lowcostmin){min=closedge[j].lowcost;k=j;}}printf((%c,%c,%d),G-vexs[closedge[k].adjvex],G-vexs[k],min);closedge[k].lowcost=TURE;for(j=0;jG-n;j++)if(closedge[j].lowcost!=TURE)if(G-edgs[k][j]closedge[j].lowcost||closedge[j].lowcost==0){closedge[j].lowcost=G-edgs[k][j];closedge[j].adjvex=k;}}}voidKruskal(MGraph*G){intk=0,m=0,n=0;intvf1,vf2,min,vset[100];for(inti=0;iG-n;i++)for(intj=0;jG-n;j++)最小生成树及其算法5if(G-edgs[i][j]!=0){if(i=j){A[k].v1=i;A[k].v2=j;A[k].cost=G-edgs[i][j];k++;}}n=0;while(m=G-e-1){min=999;for(i=n;ik;i++)if(A[i].costmin){B[n].v1=A[i].v1;B[n].v2=A[i].v2;B[n].cost=A[n].cost;min=A[i].cost;}n++;m++;}for(i=0;iG-n;i++){vset[i]=i;}k=0;while(k=G-e){vf1=B[k].v1;vf2=B[k].v2;if(vset[vf1]!=vset[vf2]){printf((%c,%c,%d),G-vexs[B[k].v1],G-vexs[B[k].v2],B[k].cost);vset[vf2]=vset[vf1];}k++;}}intmain(void){MGraph*G,a;charch1;intchoice;G=&a;printf(\n\t\t建立图的邻接矩阵\n);GreateMGraph(G);/*printf(\n\t\t已建立一个邻接矩阵！\n);for(i=0;iG-n;i++){printf(\n\t\t);for(j=0;jG-n;j++)printf(%5d,G-edgs[i][j]);最小生成树及其算法6}*/getchar();ch1=1;while(ch1==1){printf(\n);printf(\n\t\t最小生成树);printf(\n\t\t**************************);printf(\n\t\t*1——prim算法*);//printf(\n\t\t*2——kruskal算法*);printf(\n\t\t*0——退出*);printf(\n\t\t**************************);printf(\n\t\t请选择菜单号0--1：);scanf(%d,&choice);getchar();switch(choice){case1:printf(\n\t\tprim算法输出为：);prim(G,0);break;case2:printf(\n\t\tKruskal算法输出为：);Kruskal(G);break;case0:ch1=0;break;default:printf(\n\t\t输入错误！请重新输入!);}}return0;}4．应用prim算法的例子•如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.最小生成树及其算法7最小生成树及其算法8所以1+4+9+3+17+23=57.参考文献【1】《数据结构与算法教程》第二版，李春葆等，清华大学出版社。【2】《图论及其算法》，殷剑宏等，中国科学技术大学出版社。【3】《C语言程序设计》(第三版)，谭浩强，清华大学出版社。【4】《数据结构》(C语言版)，严蔚敏吴伟民，清华大学出版社。【5】《c语言习题集与上机指导》第二版，谭浩强，高等教育出版社。最小生成树及其算法9