数据结构（C言语版本）课程设计报告最小生成树的应用

1、计算机系课程设计报告武 夷 学 院 课程设计报告课程名称：数据结构（c言语版本）设计题目：最小生成树的应用学生班级：10计科1班学生姓名：指导教师：完成日期：2012-01-05 计算机系课程设计报告 课程设计项目研究报告目录一、问题描述及基本要求1 -二、 实现本程序需要解决的问题如下1 -三、 测试数据2 -四、 算法思想3 -五、 模块划分4 -六、 算法设计与分析7 -七、 源程序11 -八、 测试数据14 -九、 课程设计项目进度表及任务分配表及任务分配表15 -十、 设计心得16 -十一 参考文献17 -计算机系课程设计报告一、为题描述及基本要求在n个城市间建立通信网络，需架设n-

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

3、m的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设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的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接

4、矩阵形式输出，以及从不同顶点开始生成的最小生成树。题目要求以及达到目标：题目要求用prim算法实现给定无向网中边e和顶点n实现生成的最小生成树，输出生成树中的各边及权值。- 18 -三、测试数据第一组顶点数（vertices）、边数（edge）：4、5起始节点（starting）、下个节点（terminal）、权值（weights）：1,2,11,3,22,4,53,4,41,4,6预测结果1、2、4第二组顶点数（vertices）、边数（edge）：6，10，起始节点（starting）、下个节点（terminal）、权值（weights）：1,2,61,3,11,4,52,3,52,5,3

5、3,5,63,4,53,6,44,6,25,6,6预测结果1、4、2、5、3 四、算法思想普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。从连通网络 n = v, e 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合u中。以后每一步从一个顶点在u中，而另一个顶点不在u中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集te中，把它的顶点加入到集合u中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合u中为止。假设n=(v，e)是一个连通网，te是n上最小生成树

6、中边的集合。则构造n的最小生成树的步骤如下： （1）初始状态，te为，u=u0，u0v； （2）在所有uu，vv-u的边(u，v) e中找一条代价最小的边(u，v)并入te，同时将v并入u；重复执行步骤（2）n-1次，直到u=v为止。在普里姆算法中，为了便于在集合u和(v-u)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。 对于每一个顶点vv-u，closestv为u中距离v最近的一个邻接点，即边 (v，closestv) 是在所有与顶点v相邻、且其另一顶点ju的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv

7、=costvclosestv，采用邻接表作为存储结构：设置一个辅助数组：lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；closest域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。用prim算法构造最小生成树的过程：五、模块划分（1）预处理#include #include #define inf 9999#define max 40#define linelenght 77（2）建立无向图int adjg(int gmax) /* 建立无向图 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(inp

8、ut the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); while(e0.5*n*(n-1)|n=max) /*最大边数为，即0.5*n*(n-1)*/ 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+) gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;kn|v2n|v11|v21) error()

9、; 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 */（3）输出无向图的邻接矩阵void pri(int gmax,int n) /* 输出无向图的邻接矩阵 */ int i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+) prin

10、tf(n%dt,i); for(j=1;j=n;j+) /* 输出边的权值 */ if(gij=inf) printf(%ct,354); else printf(%dt,gij); printf(n);void prim(int gmax,int n) /* prim函数 */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) lowcosti=g1i; /* 初始化 */ closesti=1; lowcost1=0; /* 标志顶点1加入u集合 */ for(i=2;i=n;i+) /* 形成n-1条边的生成树 */ mi

11、n=inf; k=0; for(j=2;j=n;j+) /* 寻找权值最小的一条边，并把权值赋给min */ if(lowcostjmin)&(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(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); （4）输出一条分割线int priline(int h) /* 输出一条分割线 */ int

12、 g; printf(n|); for(g=0;gh;g+) printf(*); printf(|n); （5）提示错误信息int error() /* 提示错误信息 */ printf(nn|*e*r*r*o*r*|n); printf(input errors or data overflow! please re-enternn); fflush(stdin); /* 清除缓存 */ （6）主函数void main() /* 主函数 */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(l

13、inelenght); printf(input the adjacency matrix 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，

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

16、数组都会发生相应的变化。程序模块之间的调用：在主函数中调用邻接矩阵的初始化函数，邻接矩阵的生成函数，prim算法的函数，图的构造函数，输出函数。邻接矩阵的生成函数主要解决的是边的信息存储问题，而prim算法的函数是解决计算出最小生成树的功能。详细设计和编码首先我在接下来给出总的流程： main（）调用priline()函数，即输出小*调用adjg()函数，即建立无向图，后再2次调用priline()函数调用pri()函数，即输出邻接矩阵最后调用prim（）函数，即生成最小生成树结束结果分析：本课程设计的要求对于任意给定的网和起点，用prim算法的基本思想求解出所有的最小生成树并输出这些边的权值

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

18、0#define linelenght 77int 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(e0.5*n*(n-1)|n=max) /*最大边数为，即0.5*n*(n-1)*/ error(); printf(input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e

19、); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;kn|v2n|v11|v21) 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,

20、int 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 prim(int gmax,int n) /* prim函数 */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) lowcosti=g1i; /*

21、初始化 */ closesti=1; lowcost1=0; /* 标志顶点1加入u集合 */ for(i=2;i=n;i+) /* 形成n-1条边的生成树 */ min=inf; k=0; for(j=2;j=n;j+) /* 寻找权值最小的一条边，并把权值赋给min */ if(lowcostjmin)&(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(gkjlowcostj)

22、 lowcostj=gkj; closestj=k; printf(n); int priline(int h) /* 输出一条分割线 */ int g; printf(n|); for(g=0;gh;g+) printf(*); printf(|n); int error() /* 提示错误信息 */ printf(nn|*e*r*r*o*r*|n); printf(input errors or data overflow! please re-enternn); fflush(stdin); /* 清除缓存 */ void main() /* 主函数 */ int gmaxmax,n;p

23、riline(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();八、测试数据第一组第二组九、课程设计项目进度表及任务分配表及任务分配表进度日期 进度2012-1-2搜集资料2012-1-2至3设计算法2012-1-4将问题分块，然后分块写出程序2012-1-5将每块程序衔接好，进行调试2012-1-5对程序进行最后修改，整理实验报告分配表成员座号项目内容序号陈娟45号编写程序 调试程序01谢贤根12号收集资料 调试程序02黄伟伟5号收集资料 调试程序03陈开槟13号 收集资料 word排版04十、设计