最小生成树及其算法.docx

《最小生成树及其算法.docx》由会员分享，可在线阅读，更多相关《最小生成树及其算法.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树及其算法（离散数学）大作业论文题目：最小生成树及其算法院系：电子工程学院专业：智能科学与技术学号：姓名：二零逐一年十一月摘要连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比方要在n个城市间建立通信联络网，要考虑的是怎样保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是Prim普里姆算法，另一种是Kruskal克鲁斯卡尔算法。本文主要介绍Prim普里姆算法及利用。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、具体设计、测试等各个方面具体介绍了系统的设计与实现经过，最后对系统的完成情况进行了总结。关键字

2、：prum算法最小生成树算法比拟1.有关最小生成树的概念最小生成树：连通加权图里权和最小的生成树称为最小生成树。从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。定义一图：图是有一个非空的顶点集合和一个描绘顶点之间的关系即边的集合组成。它能够形式化的定义为：G=(V,E)V=V|jVVertexTypeiE=|iV,jVVP(iV,jV)i其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描绘顶点类型，集合E中P(V,jV)的含义是：对有向图来讲用“表

3、示，i对无向图来讲用“表示，即从V到jV两个顶点之间存在边。i定义二树：树包含nn=0个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R知足一下条件：1有且仅有一个节点k0属于D，它对于关系R来讲没有前趋节点，结点k0称作树的根结点。2除根结点k0之外，D中的每个结点仅有一个前趋结点，但能够有过个后继结点。3D中能够有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和nn=0个子结点。图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A

4、.edgenn，用来存放顶点的信息和边或弧的信息。定义三邻接矩阵AdjacencyMatrix：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=v1,v2,vn。G的邻接矩阵是一个具有下列性质的n阶方阵：本文主要为无向图的邻接矩阵1无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。1无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，能够表示为某一详细应用的数据。也表示i结点能否与j结点连通。定义四生成树：假如T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。2.prim算法介绍从单一顶点开场，普里姆算法根据下面步骤逐步扩大树中所含顶点的数目，直到遍及连

5、通图的所有顶点。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算法的实现#include#defineTURE999typedefstructArcNodecharvexs10;intedgs1010;in

6、tn,e;MGraph;structedgintv1;intv2;intcost;A10,B10;/创立图voidGreateMGraph(MGraph*G)inti,j,k,weight,m,n;intch1,ch2;chara,b;printf(ntt输入顶点数边数(格式如:34):);scanf(%d%d,&(G-n),&(G-e);/输入顶点数,边数for(i=0;in;i+)getchar();printf(ntt请输入第%d个顶点:,i+1);scanf(%c,&(G-vexsi);/输入顶点for(i=0;in;i+)for(j=0;jn;j+)G-edgsij=0;for(k=

7、0;ke;k+)/getchar();printf(ntt请输入第%d条边的顶点权值(格式如:ij):,k+1);getchar();scanf(%c%c%d,&a,&b,&weight);/scanf(%c,/getchar();/scanf(%c,m=0;n=0;for(m=0;G-vexsm!=a;m+);for(n=0;G-vexsn!=b;n+);/printf(ntt请输入权值:);scanf(%d,&weight);ch1=m;ch2=n;G-edgsch1ch2=weight;G-edgsch2ch1=weight;voidprim(MGraph*G,intv)inti,j,k

8、,min;structintadjvex;intlowcost;closedge10;for(i=0;in;i+)/初始化closedgei.lowcost=G-edgsvi;closedgei.adjvex=v;closedgev.lowcost=TURE;for(i=1;in;i+)min=100;/*100为允许的最大权值*/for(j=0;jn;j+)if(closedgej.lowcost!=TURE&closedgej.lowcost!=0)if(closedgej.lowcostvexsclosedgek.adjvex,G-vexsk,min);closedgek.lowcost

9、=TURE;for(j=0;jn;j+)if(closedgej.lowcost!=TURE)if(G-edgskjedgskj;closedgej.adjvex=k;voidKruskal(MGraph*G)intk=0,m=0,n=0;intvf1,vf2,min,vset100;for(inti=0;in;i+)for(intj=0;jn;j+)if(G-edgsij!=0)if(iedgsij;k+;n=0;while(me-1)min=999;for(i=n;in;i+)vseti=i;k=0;while(ke)vf1=Bk.v1;vf2=Bk.v2;if(vsetvf1!=vset

10、vf2)printf(%c,%c,%d),G-vexsBk.v1,G-vexsBk.v2,Bk.cost);vsetvf2=vsetvf1;k+;intmain(void)MGraph*G,a;charch1;intchoice;G=&a;printf(ntt建立图的邻接矩阵n);GreateMGraph(G);/*printf(ntt已建立一个邻接矩阵！n);for(i=0;in;i+)printf(ntt);for(j=0;jn;j+)printf(%5d,G-edgsij);*/getchar();ch1=1;while(ch1=1)printf(n);printf(ntt最小生成树);

11、printf(ntt*);printf(ntt*1prim算法*);/printf(ntt*2kruskal算法*);printf(ntt*0退出*);printf(ntt*);printf(ntt请选择菜单号0-1：);scanf(%d,&choice);getchar();switch(choice)case1:printf(nttprim算法输出为：);prim(G,0);break;case2:printf(nttKruskal算法输出为：);Kruskal(G);break;case0:ch1=0;break;default:printf(ntt输入错误！请重新输入!);return0;4应用prim算法的例子?如下列图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价单位：万元，试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.所以1+4+9+3+17+23=57.参考文献【1】（数据构造与算法教程）第二版，李春葆等，清华大学出版社。【2】（图论及其算法），殷剑宏等，中国科学技术大学出版社。【3】（C语言程序设计）(第三版)，谭浩强，清华大学出版社。【4】（数据构造）(C语言版)，严蔚敏吴伟民，清华大学出版社。【5】（c语言习题集与上机指导）第二版，谭浩强，高等教育出版社。