PRIM算法求最小生成树.doc

一、问题分析和任务定义 在该部分中主要包括两个方面：问题分析和任务定义；1 问题分析本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。在实现该本设计功能之前，必须弄清以下三个问题：11 关于图、网的一些基本概念111 图 图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常，V（G）和E（G）分别表示图G的顶点集合和边集合。E（G）也可以为空集。则图G只有顶点而没有边。112 无向图 对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。113 子图 设有两个图G=（V，E）G=（V，）,若V是V的子集，即VV ，且E是E的子集，即EE ，称G是G的子图。114 连通图 若图G中任意两个顶点都连通，则称G为连通图。115 权和网 在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。把边上带权的图称为网。如图1所示。12 理解生成树和最小生成树之间的区别和联系121 生成树 在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G，即：V（G）= V（G）和E（G）E（G），若边集E（G）中的边既将图中的所有顶点连通又不形成回路，则称子图G是原图G的一棵生成树。122 最小生成树 图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。如图1所示。26152网最小生成树4132655213441365665534图1网转化为最小生成树13 理解PRIM（普里姆）算法的基本思想131 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），其中ViU,Vj(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge ，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。 132 在PRIM算法中需要解决的两个问题在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来；每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次（1kn-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量INFINIT的边在内，从如此多的边中查找最短边，其时间复杂度为O(k(n-k)，显然是很费时的，是否有一种好的方法能够降低查找最短边的时间复杂度。133 上述问题的解决方法针对中出现的问题可以通过在算法中实现，详情请看PRIM算法的基本思想；针对中出现的问题，通过对PRIM算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。2 任务定义通过以上的分析和理解，对本设计分别从以下三个方面进行分析：21 输入数据的类型在本次设计中，是对无向网进行操作，网中的顶点数、边数、顶点的编号及每条边的权值均通过键盘输入，它们的数据类型均为整型，其中，权值的范围为032768（即“”）；22 输出数据的类型当用户将无向网创建成功以后，就可以通过键盘任意输入一个起点值将其对应的最小生成树的生成路径及权值显示出来；23 测试数据本次设计中是通过用PRIM算法求最小生成树，分别用以下三组数据进行测试： 231 假定在创建无向网时只输入一个顶点，如图2所示，验证运行结果1 图2单一节点的图232 假定创建的无向网如图3所示，验证运行结果43266566655521341图3网中存在权值相等的边233 假定创建的无向网如图4所示，验证运行结果 41326516191875621143311图4网中边的权值各不相等二、概要设计和数据结构的选择在本次设计中，网的定义为G=(V,E),V表示非空顶点集,E表示边集,其存储结构这里采用邻接矩阵的方式来存储。1 数据类型的定义在本设计中所涉及到的数据类型定义如下：1.1 符号常量的定义算法中涉及到两个符号常量，定义如下：#define MAX 20 功能：用于表示网中最多顶点个数；#define INFINIT 32768 功能：用于表示权的最大值，即。1.2 结构体的定义整个算法中涉及的结构体定义如下：121 定义结构体ArcNode功能：用于存放边的权值typedef struct int adj;/权值ArcNode;122 定义结构体AdjMatrix功能：用于表示网的结构及存储方式。typedef structint vexsMAX；/vexs表示顶点向量int vexnum,arcnum；/分别表示图的顶点数和弧数*/ArcNode arcsMAXMAX；/邻接矩阵AdjMatrix;123 定义结构体Node功能：用于表示求最小生成树时用到的辅助数组。typedef structint adjvex;/存放顶点编号int lowcost;/存放顶点权值Node;1.3 外部变量的定义算法中涉及到两个外部变量，定义如下： Node closeMAX 功能：存放每个顶点所连接的边所对应的权值；int flag=0 功能：标志变量，当创建网时，输入的顶点个数=1时，直接输出“不存在最小生成树”程序不在往后执行，否则继续往下执行。2 概要设计在本设计中，主要包括六个函数模块，其算法思想和功能描述如下：21 子函数int Locate(AdjMatrix *G,int V)功能：是求出某个顶点在顶点向量表中的位置，在其函数体中通过for循环将某一顶点与顶点向量表中的所有顶点进行比较，当出现两者相等时，将该顶点在vexsMAX数组中的下标通过return语句返回，否则返回-1；22 子函数AdjMatrix *creat(AdjMatrix *G)功能：是完成无向网的创建，在其函数体中，首先通过键盘输入网中顶点数，若顶点个数vexnum)，其中，调用函数Minium()求出辅助数组close中权值最小的边, 并将其在辅助数组中的相应位置返回到主调函数中并赋给k0，此时closek0中存有当前最小边(u0, v0)的信息，将边所对应的终点放入p的顶点向量表中，累加边的权值；然后，输出；最后，在顶点v0并入U之后,利用for循环更新closedgei；当所有的顶点v0都纳入U集合之后，输出最小生成树中的顶点序列及最小生成树的权值之和。25 子函数void display(AdjMatrix *G)功能：是创建的无向网所对应的邻接矩阵；26 主函数void main()功能：是完成对上述各子函数的调用，完成本次设计的要求，在其函数体中，通过while循环可以实现重复创建网以及可以从网中的不同顶点出发求出对应的最小生成树。3 程序流程图通过上述概要设计，各程序模块之间的层次（调用）关系，用流程图表示如下：开 始输入ch, 用于判断是否创建无向网ch=Y1 调用create()函数flag=02调用display()函数st=03调用prim ()函数4调用Minium ()函数 否 是 否 是输入起点st 是 否结 束图5流程图上述流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display()函数输出；最后调用prim ()函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用Minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。 三、详细设计和编码各程序模块代码如下：1 子函数int Locate(AdjMatrix *G,int V)功能：是求出某个顶点在顶点向量表中的位置，代码如下：int Locate(AdjMatrix *G,int V) /求顶点位置函数int j=-1,k;for(k=0;kvexnum;k+) /求V在顶点向量表中的位置if(G-vexsk=V) j=k;break;return j;2 子函数AdjMatrix *creat(AdjMatrix *G)功能：是完成无向网的创建，代码如下：AdjMatrix *creat(AdjMatrix *G) /创建无向网int i,j,k,v1,v2,weight,m=1;printf(请输入网中的顶点数：);scanf(%d,&G-vexnum);if(G-vexnum=1) coutn最小生成树不存在!arcnum); for(i=0;ivexnum;i+) /初始化邻接矩阵for(j=0;jvexnum;j+) if(i=j) G-arcsij.adj=0; else G-arcsij.adj=INFINIT; printf(请输入网中的顶点编号：); for(i=0;ivexnum;i+)/输入网中的顶点编号 scanf(%d,&G-vexsi);printf(输入每条弧所对应的两个顶点及权值!n); for(k=0;karcnum;k+) cout请输入第m+v1v2weight; /输入一条弧的两个顶点及权值 i=Locate(G,v1);/ 求一条弧的两个顶点在顶点向量表中的位置 j=Locate(G,v2); G-arcsij.adj=weight; G-arcsji.adj=weight; return(G);3 子函数int Minium(AdjMatrix *G,Node close)功能：是求出辅助数组close中权值最小的边，代码如下：int Minium(AdjMatrix *G,Node close)/close中权值最小的边int i,min,k;min=INFINIT;/置最小权值为INFINITfor(i=0;ivexnum;i+) /找出辅助数组close中权值最小的边if(closei.lowcostvexsn+=u; closek.lowcost=0;/初始化U=u for(i=0;ivexnum;i+) if(i!=k) /对V-U中的顶点i,初始化closei closei.adjvex=u; closei.lowcost=G-arcski.adj; for(j=1;jvexnum-1;j+)/找n-1条边(n=G-vexnum) k0=Minium(G,close);/closek0中存有当前最小边(u0, v0)的信息 u0=closek0.adjvex;/u0U v0=G-vexsk0; /v0V-U p-vexsn+=v0;/将终点放入数组中s+=closek0.lowcost;/求最小生成树的权值之和 cout u0v0tclosek0.lowcostendl; /输出最小生成树的路径 closek0.lowcost=0;/将顶点v0纳入U集合 for(i=0;ivexnum;i+)/在顶点v0并入U之后,更新closedgei if(G-arcsk0i.adjarcsk0i.adj; closei.adjvex=v0; coutn最小生成树中的顶点序列为：;for(i=0;ivexnum;i+) cout vexsi ;coutendl;coutn最小生成树的权值之和为：sendl;5 子函数void display(AdjMatrix *G)功能：是创建的无向网所对应的邻接矩阵；代码如下：void display(AdjMatrix *G) /输出邻接矩阵算法int i,j;for(i=0;ivexnum;i+)couttvexsi;coutendl;cout;for(i=0;ivexnum;i+)cout;coutendl;for(i=0;ivexnum;i+) cout vexsi ; for(j=0;jvexnum;j+) if(G-arcsij.adj=INFINIT) coutt; else couttarcsij.adj; coutendl; for(i=0;ivexnum;i+)cout; coutendl;四、上机调试1 程序调试中遇到的问题和解决方法11 在编译时，出现有些库函数没有定义和警告错误；解决方法：需要在程序首部加入以下包含文件：#includestdio.h、#includestring.h、#includemalloc.h、#include iomanip.h；出现的警告错误是由于定义一指针变量时，需用库函数malloc（）为其分配内存空间12 在创建无向网函数creat()中，当输入的顶点个数=1时，由于其不满足网的定义，因此如何求其最小生成树；当通过键盘分别输入边所关联的两个顶点和权值时，用语句“scanf(“%d%d%d”, v1,v2,weight)”输入时，会导致结果出现错误；解决方法：通过在函数首部定义一标记变量flag，将其初始化为0，当输入的顶点个数v1v2weight; ” 输入边所关联的两个顶点和权值； 13 在函数Minium()中，当用语句“min=close0.lowcost”初始化min时，会导致结果出现错误；解决方法：用语句“min=INFINIT;”可以将其置为；14 在普里姆算法函数prim()，如何将最小生成树中的顶点序列显示出来；解决方法：首先，定义AdjMatrix结构体类型的指针变量*p，并通过语句“p-vexsn+=u;”将起点存入顶点向量表中，然后在for循环体中用语句“p-vexsn+=v0;”将每条边的终点依次放入顶点向量表中，最后向量表中的数据就是最小生成树中的顶点序列，通过fou循环将其输出；15 在输出邻接矩阵函数display()中，如何将矩阵中值为INFINIT的元素在屏幕上用显示；解决方法：通过if判断语句“if(G-arcsij.adj=INFINIT) coutt;”达到要求；16 在主函数main()中，当前一次创建网时输入的顶点个数1时，此时若求最小生成树时，得到的结果将出错。解决方法：需在main()函数的第一层while()循环体的最后加入语句“flag=0;”，因为在创建函数creat()中，当第一次创建网时输入的顶点个数1时，由于flag此时为1，所以仍将其按照第一种情况处理，从而导致结果出错；2 性能分析利用PRIM算法生成最小生成树时，求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。3 心得与体会在整个课程设计的过程中，首先，应该根据课题的要求对题意进行分析，将所遇到的问题进行归纳和总结，在本设计中，题意要求对给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树，我们应该了解关于网的一些基本概念和生成树与最小生成树之间有何区别和联系，主要是要明确的理解PRIM算法的基本思想。其次，针对出现的问题查找相关资料将其解决，主要应该查找有关PRIM算法基本思想方面的详细介绍，当所有的问题得到解决后，对本设计应该有个整体的思路并通过编写各个函数模块去实现课题的功能；最后，将编写的源程序代码在计算机上调试运行，直至调试成功。本次课程设计，让我对所学的知识有了一次综合运用的机会,通过实践，提高了自己在分析问题、解决问题和编写算法方面的能力，从而对所学的知识有了更加深刻的理解和掌握，受益匪浅。希望以后学校能多提供这样的机会给我们锻炼，使我们能够为学所用，真正增长我们的才干。五、用户使用说明在本设计中，是通过给定任意网和起点求出最小生成树。程序最大顶点数和边数规定为20（可以在程序中任意设定大小）。当编译、运行之后，屏幕会显示如下信息，用户可以根据以下使用说明做相关操作：1 请输入网中的顶点数。您可以输入在定义范围之内的任意值，当输入的顶点数=1时，会显示“最小生成树不存在!”2 请输入网中的边数。根据用户自己定义 3 请输入网中的顶点编号。分别输入网中的所有顶点4 输入每条弧所对应的两个顶点及权值。分别输入起点、终点和权值，输入时两者之间以空格隔开5 请输入起点。输入从网中的哪个顶点出发，生成最小生成树，可以输入网中的任意顶点，若输入的起点不是网中的某一顶点则显示“输入起点有错，请重新输入!”若想退出此操作则输入06 继续创建无向网请输入Y,否则按任意键。 如果用户想再次创建网并做相关操作，则输入Y或y否则输入任意字符退出运行环境六、测试结果该部分是对前面任务定义中的测试数据进行验证和分析。1 假定在创建的无向网只含有1个顶点，如图2所示，运行结果如下所示： 分析：从上图可以看出，由于顶点数为1，不符和网的性质，所以不存在最小生成树！2 假定创建的无向网的顶点个数1，并且网中有些边的权值相等，运行结果如下图所示：21 创建部分如下：22 运行结果如下：分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩阵中用表示，由于是以顶点1作为起点生成最小生成树，所以上述运行结果对应的生成树如图1所示。3 假定创建的无向网的顶点数1，并且网中的边的权值都不等，运行结果如下所示：31 创建部分如下：32 运行结果如下：41326516191875621143311分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩阵中用表示，由于是以顶点1作为起点生成最小生成树，所以上述运行结果对应的生成树如图所示：16413265185611网最小生成树图无向网转化为最小生成树七、参考资料1徐孝凯，数据结构实用教程，清华大学出版社，2005年7月。2赫阿朋，C+应用编程，电子工业出版，2003年4月。3谭浩强，C语言程序设计教程，高等教育出版社，2004年5月。八、附录 带注释的源程序：#includestdio.h#includestring.h#includemalloc.h#includeiostream.h#include iomanip.h#define MAX 20 /最多顶点个数#define INFINIT 32768/表示极大值，即typedef structint adj; /adj是权值类型ArcNode;typedef structint vexsMAX,vexnum,arcnum;/*vexs表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ArcNode arcsMAXMAX; /*邻接矩阵*/AdjMatrix;typedef structint adjvex;/存放顶点编号int lowcost;/存放顶点权值Node; Node closeMAX;/求最小生成树时的辅助数组int flag=0;int Locate(AdjMatrix *G,int V) /求顶点位置函数int j=-1,k;for(k=0;kvexnum;k+)if(G-vexsk=V) j=k;break;return j;AdjMatrix *creat(AdjMatrix *G) /创建无向网int i,j,k,v1,v2,weight,m=1;printf(请输入网中的顶点数：);scanf(%d,&G-vexnum);if(G-vexnum=1) coutn*最小生成树不存在!* *arcnum); for(i=0;ivexnum;i+) /初始化邻接矩阵 for(j=0;jvexnum;j+) if(i=j) G-arcsij.adj=0; else G-arcsij.adj=INFINIT; printf(请输入网中的顶点编号：); /输入网中的顶点编号 for(i=0;ivexnum;i+) scanf(%d,&G-vexsi); printf(输入每条弧所对应的两个顶点及权值!n); for(k=0;karcnum;k+) cout请输入第m+v1v2weight; /输入一条弧的两个顶点及权值 i=Locate(G,v1); j=Locate(G,v2); G-arcsij.adj=weight; G-arcsji.adj=weight;return(G);int Minium(AdjMatrix *G,Node close)/close中权值最小的边int i,min,k;min=INFINIT;/置最小权值为INFINITfor(i=0;ivexnum;i+)if(closei.lowcostvexsn+=u; closek.lowcost=0;/初始化U=u for(i=0;ivexnum;i+) if(i!=k) /对V-U中的顶点i,初始化closeiclosei.adjvex=u; closei.lowcost=G-arcski.adj; for(j=1;jvexnum-1;j+)/找n-1条边(n=G-vexnum) k0=Minium(G,close);/closek0中存有当前最小边(u0, v0)的信息 u0=closek0.adjvex;/u0U v0=G-vexsk0; /v0V-U p-vexsn+=v0;/将终点放入数组中s+=closek0.lowcost;/求最小生成树的权值之和 cout u0v0tclosek0.lowcostendl; /输出最小生成树的路径 closek0.lowcost=0;/将顶点v0纳入U集合