数据结构最小生成树普利姆算法

1、一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。求解如何以最低经济代价建设此通信网，这是一个最小生成树问题。要求：（1）利用普利姆算法求网的最小生成树；（2）输出生成树中各边及权值。 二、实现本程序需要解决的问题如下(1)、如何选择存储结构去建立一个带权网络。(2)、如何在所选存储结构下输出这个带权网络。(3)、如何实现PRIM算法的功能。(4)、如何从每个顶点开始找到所有的最小生成树的顶点。(5)、如何输出最小生成树的边及其权值。此问题的关键在于如何实现PRIM算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。首先

2、我们对问题进行大致的概要分析：这个问题主要牵涉到通过PRIM的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储

3、，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始省城的最小生成树。题目要求以及达到目标：题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。三、测试数据第一组顶点数（vertices）、边数（edge）：2、1起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、5，预测结果<1,2>5第二组顶点数（vertices）、边数（edge）：3、3起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、4 1、3、5 2、3、6预测结果

4、<1,2>4、<1,3>5第三组顶点数（vertices）、边数（edge）：4、5，起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、3 1、3、4 1、4、6 2、4、7 3、4、5预测结果<1,2>3、<1,3>4、<1,4>6 四、算法思想Prim算法求最小生成树的主要思想此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u

5、,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。 五、模块划分（1）预处理#include <stdio.h>#include <graphics.h>#define inf 9999#define max 40#define linelenght 77（2）普里姆算法void prim(int gmax,int n) /* prim的函数 */

6、int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) /* n个顶点，n-1条边 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 顶点未加入到最小生成树中 */ lowcost1=0; /* 标志顶点1加入U集合 */ for(i=2;i<=n;i+) /* 形成n-1条边的生成树 */ min=inf; k=0; for(j=2;j<=n;j+) /* 寻找满足边的一个顶点在U,另一个顶点在V的最小边 */ if(lowcostj<min)&&(lowc

7、ostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); lowcostk=0; /* 顶点k加入U */ for(j=2;j<=n;j+) /* 修改由顶点k到其他顶点边的权值 */ if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf("n"); （3）输出分割线int priline(int h) /* 输出一条分割线 */ int g; printf("n|"); for(g=0;g<h;g+

8、) printf("*"); printf("|n"); （4）提示错误信息int error() /* 提示错误信息 */ printf("nn|*E*R*R*O*R*|n"); printf("Input errors or Data overflow! please re-enternn"); fflush(stdin); /* 清除缓存 */ （5）建立无向图int adjg(int gmax) /* 建立无向图 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(&qu

9、ot;Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); while(e<=0|e>=n*(n-1)|n>=max) error(); printf("Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) for(j=1;j<=n;j+)

10、gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;k<=e;k+) printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); while(v1=v2|v1>n|v2>n|v1<1|v2<1) error(); printf("Input the %d on the edge of the sta

11、rting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回节点个数n */（6）输出无向图的邻接矩阵void pri(int gmax,int n) /* 输出无向图的邻接矩阵 */ int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;i<=n;i+) printf("n%dt&

12、quot;,i); for(j=1;j<=n;j+) /* 输出边的权值 */ if(gij=inf) printf("%ct",'354'); else printf("%dt",gij); printf("n");（7）主函数模块void main() /* 主函数 */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf("Input the adjacency m

13、atrix without directed graph:n"); pri(g,n); printf("n"); printf("Minimum spanning tree structure:n"); prim(g,n); getch();六、算法设计与分析（1）关于带权网络的存储形式 要实现对于任意给定带权网络和顶点，运用PRIM基本算法思想求解所有的最小生成树的运算。在这里我们首先要明确所选用的数据结构，即选用何种数据结构存储来存储带权网络，这是必选首先解决的问题，所以我们选择了图的邻接矩阵存储方式来存储带权网络，建图时采用邻接矩阵的结构

14、，定义邻接矩阵用到了一维数组和二维数组，分别存储顶点信息和边的权值。由于该算法对图中的边的权值频繁比较，所以采用邻接矩阵比较方便，并在此基础上实现带权网络的建立以及输出显示。（2）关于普利姆算法的基本思想Prim算法求最小生成树的主要思想此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树

15、。对于最小生成树问题最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。（3）概要设计通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各边的权值的比较修改，在普利姆算法中，为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点viV-U,在辅助数组中存在一个相应分量closedgei-1，他包括两个域，其中lowcost存储该边上的权值。显然，closedgei-1.lowcost=Mincost(u,vi)| uU从算法可以看出每加入一个顶点到U中，closedge数组都会发生相应的变

16、化。程序模块之间的调用：在主函数中调用邻接矩阵的初始化函数，邻接矩阵的生成函数，PRIM算法的函数，图的构造函数，输出函数。邻接矩阵的生成函数主要解决的是边的信息存储问题，而PRIM算法的函数是解决计算出最小生成树的功能。详细设计和编码首先我在接下来给出总的流程：Main（）建立图并初始化图中信息调用主函数prim找到顶点I信息，并将其加入到数组closedge中与I相邻的顶点，将它们与之比较，最小的放入cloedgei.lowcost中将找到的所有定点信息都给K，并输出closedgek.adjvex,closedgek.lowcost G.vexsk结束Main（）结果分析：本课程设计的要

17、求对于任意给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树并输出这些边的权值，所以如何实现输出显示所有的最小生成树关键问题所在，经过分析调试，用一个for语句就可以解决这个问题，从每个顶点出发，开始每一次遍历并输出显示出来。算法的时间和空间性能分析根据程序中算法的循环语句可以判断出普利姆算法的时间复杂度为O（n2）算法和图中的边数无关。因此普利姆算法适合求稠密网的最小生成树，因为在算法中用邻接矩阵的存储结构，在无向图中，邻接矩阵是对称的。所以仅需要存储上三角或下三角的元素，因此需要n(n+1)的存储空间。测试结果界面的截图输入的情况的截图输出结果的截图输入错误的截图七、源程序源程

18、序代码（有注释详解）#include <stdio.h>#include <graphics.h>#define inf 9999#define max 40#define linelenght 77void prim(int gmax,int n) /* prim的函数 */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) /* n个顶点，n-1条边 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 顶点未加入到最小生成树中 */ lowcost1=0; /*

19、 标志顶点1加入U集合 */ for(i=2;i<=n;i+) /* 形成n-1条边的生成树 */ min=inf; k=0; for(j=2;j<=n;j+) /* 寻找满足边的一个顶点在U,另一个顶点在V的最小边 */ if(lowcostj<min)&&(lowcostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); lowcostk=0; /* 顶点k加入U */ for(j=2;j<=n;j+) /* 修改由顶点k到其他顶点边的权值 */ if(gkj

20、<lowcostj) lowcostj=gkj; closestj=k; printf("n"); int priline(int h) /* 输出一条分割线 */ int g; printf("n|"); for(g=0;g<h;g+) printf("*"); printf("|n"); int error() /* 提示错误信息 */ printf("nn|*E*R*R*O*R*|n"); printf("Input errors or Data overflow!

21、please re-enternn"); fflush(stdin); /* 清除缓存 */ int adjg(int gmax) /* 建立无向图 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf("Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); while(e<=0|e>=n*(n-1)|n>=max) error(); printf("Input the n

22、umber of vertices, number of the edge:"); scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) for(j=1;j<=n;j+) gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;k<=e;k+) printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&

23、v1,&v2,&weight); while(v1=v2|v1>n|v2>n|v1<1|v2<1) error(); printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回节点个数n */void pri(int gmax,int

24、n) /* 输出无向图的邻接矩阵 */ int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;i<=n;i+) printf("n%dt",i); for(j=1;j<=n;j+) /* 输出边的权值 */ if(gij=inf) printf("%ct",'354'); else printf("%dt",gij); printf("n");void main() /* 主函数 */ int gmaxmax,n;

25、priline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf("Input the adjacency matrix without directed graph:n"); pri(g,n); printf("n"); printf("Minimum spanning tree structure:n"); prim(g,n); getch();八、测试数据第一组第二组第三组九、课程设计项目进度表及任务分配表及任务分配表进度日期 进度201

26、1-1-15搜集资料2011-1-16至17设计算法2011-1-18 将问题分块，然后分块写出程序2011-1-19将每块程序衔接好，进行调试2011-1-20对程序进行最后修改，整理实验报告分配表成员座号项目内容序号蒋家权15号编写程序 调试程序01陈相财25号编写程序 调试程序02吴继伟6号收集资料 调试程序03梁丽春7号 收集资料 调试程序04十、设计心得 我们设计的题目是最小生成树的构造，在这次实践中遇到了各种问题，碰到问题有时总是百思不得其解最开始，程序要求输入数值时，如果任意没有按照程序给定的类型输入，程序就会出现死循环，虽然加入了检测程序段，但是当我们不按个数输入的时候程序也出现了不稳定，又进入死循环了。我们想了很多办法，其中之一就是加入break这个函数。不过，并没有出项我们想要的结果，导致循环检测输入的函数while无法继续执行，中途就中