最小生成树算法及其算法.doc

_包头师范学院本 科 学 年 论 文论文题目： 最小生成树及其算法 院 系： 数学科学学院 专 业： 信息与计算科学 学 号： 0800000062 姓 名： 吉余 指导教师： 吴云 撰写学年： 2010 至2011 学年 二零一零 年 十一 月目录1有关最小生成树的概念12 prim算法介绍23 prim算法的实现34 kruskal算法介绍 85 kruskal算法的实现96算法比较12参考文献13-可编辑修改-摘 要连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。本文重点讲述prum算法和kruskai算法和比较。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键字：prum算法、最小生成树 kruskal算法 算法比较1 有关最小生成树的概念最小生成树：连通加权图里权和最小的生成树称为最小生成树。从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：G=(V,E)V= | VertexTypeE=|,VP(,)其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描述顶点类型，集合E中P(,)的含义是：对有向图来说用“”表示，对无向图来说用“（）”表示，即从到 两个顶点之间存在边。定义二（树）：树包含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.edgenn，用来存放顶点的信息和边或弧的信息。定义三（邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=v1,v2,vn。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）（1） 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。定义四（生成树）：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。2 prim算法介绍最小生成树的两个著名算法：prim算法和克鲁斯卡尔算法2 ,本文应用的是prim算法。则克鲁斯卡尔算法则不进行描述了。Prim算法的基本思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。PRIM算法介绍：设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge存放选择需要的数据,先把下标0对应点放入U中, closedgei.uxiabiao=0,(因为U中只有下标0这一个点), closedgei.lowcost中存放其他点到下标为0的点的权,closedge0.lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min，用擂台式比较法选出closedgej.lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为U中又加入了一个点，所以要修改closedgei.lowcost的值，比较新选中点与V-U中点的权和原来的closedgei.lowcost,取小的那个存入。然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。本程序采用数组存储结构进行存储，把第一个点所到的边记录下来，然后把权值最小的边存入数组，同时将刚才所存边的的终点作为起点再次记录该点所到的边，并记录权值最小的边存入数组，这个过程中，已经被访问的点不再访问。知道最后所有的权值最小的边全部输出。这就是PRIM算法求最小生成树。3 prim算法的实现void prim(MGraph G)for (i=1; iG.vertexNum;i+)lowcosti=G.arc0i;adjvexi=0;lowcost0=0;for (i=1;iG.vertexNum;i+)k=MinEdge(lowcost,G.vertexNum)cout(kadjvexk)lowcostk;lowcostk=0;for (j=1;jG.vertexNum;j+)if G.arckjlowcostjlowcostj=G.arckj;adjvexj=k;#include /* INT_MAX等 */#include /* EOF(=Z或F6),NULL */#include#include /* floor(),ceil(),abs() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK*/typedef int VRType;typedef char InfoType;#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */typedef char VertexTypeMAX_NAME;#define INFINITY INT_MAX /* 用整型最大值代替 */#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */typedef enumDG,DN,AG,ANGraphKind; /* 有向图,有向网,无向图,无向网 */typedef structVRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */ /* 对带权图，c则为权值类型 */InfoType *info; /* 该弧相关信息的指针(可无) */ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; /* 顶点向量 */AdjMatrix arcs; /* 邻接矩阵 */int vexnum,arcnum; /* 图的当前顶点数和弧数 */GraphKind kind; /* 图的种类标志 */MGraph; /*图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作*/int LocateVex(MGraph G,VertexType u) /* 初始条件:图G存在,u和G中顶点有相同特征 */* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i;return -1;Status CreateAN(MGraph *G) /* 采用数组(邻接矩阵)表示法,构造无向网G。*/int i,j,k,w,IncInfo;char sMAX_INFO,*info;VertexType va,vb;printf(请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): );scanf(%d,%d,%d,&(*G).vexnum,&(*G).arcnum,&IncInfo);printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;+i) /* 构造顶点向量 */scanf(%s,(*G).vexsi);for(i=0;i(*G).vexnum;+i) /* 初始化邻接矩阵 */for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=INFINITY; /* 网 */(*G).=NULL;printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,(*G).arcnum);for(k=0;k(*G).arcnum;+k)scanf(%s%s%d%*c,va,vb,&w); /* %*c吃掉回车符 */i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.adj=(*G).arcsji.adj=w; /* 无向 */if(IncInfo)printf(请输入该边的相关信息(%d个字符): ,MAX_INFO);gets(s);w=strlen(s);if(w)info=(char*)malloc(w+1)*sizeof(char);strcpy(info,s);(*G).=(*G).=info; /* 无向 */(*G).kind=AN;return OK;typedef struct /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */VertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;int minimum(minside SZ,MGraph G) /* 求closedge.lowcost的最小正值 */int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; /* 第一个不为0的值 */k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;void MiniSpanTree_PRIM(MGraph G,VertexType u) /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j) /* 辅助数组初始化 */if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; /* 初始,U=u */ printf(最小代价生成树的各条边为:n); for(i=1;iG.vexnum;+i) /* 选择其余G.vexnum-1个顶点 */ k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */ printf(%s-%s)n,closedgek.adjvex,G.vexsk); /* 输出生成树的边 */ closedgek.lowcost=0; /* 第K顶点并入U集 */ for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost) /* 新顶点并入U集后重新选择最小边 */strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;int main()MGraph G;CreateAN(&G);MiniSpanTree_PRIM(G,G.vexs0);getch();return 0;4 kruskal算法介绍kruskal算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。krukal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。假设 WN=(V,E) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。5 Kruskal算法实现#include#includeusing namespace std;int p1001,rank1001;int cho1001;struct edgeint u,v,w;/u表示起始点编号，v表示终点编号，w表示该路径费用e15001;int n,m;/n表示点的个数，m表示路径数void Init()int i;for(i=1;i=n;i+)pi=i;ranki=0;bool cmp(edge a,edge b)return a.wranky)py