最小生成树的应用

计算机系课程设计报告武夷学院课程设计报告课程名称：数据结构（C言语版本）设计题目：最小生成树的应用学生班级：10计科1班学生姓名：陈娟，谢贤根，黄伟伟，陈开槟指导教师：林丽惠完成日期：2012-01-05计算机系课程设计报告课程设计项目研究报告目录一、问题描述及基本要求.......................................................................................-1-二、实现本程序需要解决的问题如下.................................................................-1-三、测试数据.........................................................................................................-2-四、算法思想.........................................................................................................-3-五、模块划分..............................................................................错误!未定义书签。六、算法设计与分析.............................................................................................-7-七、源程序...........................................................................................................-11-八、测试数据.......................................................................................................-14-九、课程设计项目进度表及任务分配表及任务分配表...................................-15-十、设计心得.......................................................................................................-16-十一参考文献.......................................................................................................-17-计算机系课程设计报告-1-一、为题描述及基本要求在n个城市间建立通信网络，需架设n-1条线路。求解如何以最低经济代价建设此通信网，这是一个最小生成树问题。要求：（1）利用普利姆算法求网的最小生成树；（2）输出生成树中各边及权值。二、实现本程序需要解决的问题如下(1)、如何选择存储结构去建立一个带权网络。(2)、如何在所选存储结构下输出这个带权网络。(3)、如何实现prim算法的功能。(4)、如何从每个顶点开始找到所有的最小生成树的顶点。(5)、如何输出最小生成树的边及其权值。此问题的关键在于如何实现prim算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过prim的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵形式输出，以及从不同顶点开始生成的最小生成树。题目要求以及达到目标：题目要求用prim算法实现给定无向网中边e和顶点n实现生成的最小生成树，输出生成树中的各边及权值。计算机系课程设计报告-2-三、测试数据第一组顶点数（vertices）、边数（edge）：4、5起始节点（starting）、下个节点（terminal）、权值（weights）：1,2,11,3,22,4,53,4,41,4,6预测结果1,21、1,32、3,44第二组顶点数（vertices）、边数（edge）：6，10，起始节点（starting）、下个节点（terminal）、权值（weights）：1,2,61,3,11,4,52,3,52,5,33,5,63,4,53,6,44,6,25,6,6预测结果1,31、3,64、6,42、3,25、2,53计算机系课程设计报告-3-四、算法思想普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。从连通网络N={V,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。假设N=(V，{E})是一个连通网，TE是N上最小生成树中边的集合。则构造N的最小生成树的步骤如下：（1）初始状态，TE为{}，U={u0}，u0∈V；（2）在所有u∈U，v∈V-U的边(u，v)∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U；重复执行步骤（2）n-1次，直到U=V为止。在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边(v，closest[v])是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]，采用邻接表作为存储结构：设置一个辅助数组：lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；closest域记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。用prim算法构造最小生成树的过程：计算机系课程设计报告-4-五、模块划分（1）预处理#includestdio.h#includegraphics.h#defineinf9999#definemax40#definelinelenght77（2）建立无向图intadjg(intg[][max])/*建立无向图*/{intn,e,i,j,k,v1=0,v2=0,weight=0;printf(Inputthenumberofvertices,numberoftheedge:);scanf(%d,%d,&n,&e);while(e=0||e0.5*n*(n-1)||n=max)/*最大边数为Cn2，即0.5*n*(n-1)*/{error();printf(Inputthenumberofvertices,numberoftheedge:);scanf(%d,%d,&n,&e);}for(i=1;i=n;i++)for(j=1;j=n;j++)g[i][j]=inf;/*初始化矩阵，全部元素设为无穷大*/for(k=1;k=e;k++){printf(Inputthe%dontheedgeofthestartingpoint,terminal,weights:,k);scanf(%d,%d,%d,&v1,&v2,&weight);while(v1==v2||v1n||v2n||v11||v21){error();printf(Inputthe%dontheedgeofthestartingpoint,terminal,weights:,k);scanf(%d,%d,%d,&v1,&v2,&weight);}g[v1][v2]=weight;/*无向网的邻接矩阵是对称矩阵*/g[v2][v1]=weight;}return(n);}/*返回顶点个数n*/计算机系课程设计报告-5-（3）输出无向图的邻接矩阵voidpri(intg[][max],intn)/*输出无向图的邻接矩阵*/{inti,j;for(i=0;i=n;i++)printf(%d\t,i);for(i=1;i=n;i++){printf(\n%d\t,i);for(j=1;j=n;j++)/*输出边的权值*/{if(g[i][j]==inf)printf(%c\t,'\354');elseprintf(%d\t,g[i][j]);}}printf(\n);}voidprim(intg[][max],intn)/*prim函数*/{intlowcost[max],closest[max];inti,j,k,min;for(i=2;i=n;i++){lowcost[i]=g[1][i];/*初始化*/closest[i]=1;}lowcost[1]=0;/*标志顶点1加入U集合*/for(i=2;i=n;i++)/*形成n-1条边的生成树*/{min=inf;k=0;for(j=2;j=n;j++)/*寻找权值最小的一条边，并把权值赋给min*/if((lowcost[j]min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf((%d,%d)%d\t,closest[k],k,min);lowcost[k]=0;/*顶点k加入U*/for(j=2;j=n;j++)/*修改由顶点k到其他顶点边的权值*/if(g[k][j]lowcost[j]){计算机系课程设计报告-6-lowcost[j]=g[k][j];closest[j]=k;}printf(\n);}}（4）输出一条分割线intpriline(inth)/*输出一条分割线*/{intg;printf(\n|);for(g=0;gh;g++)printf(*);printf(|\n);}（5）提示错误信息interror()/*提示错误信息*/{printf(\n\n|************************E*R*R*O*R************************|\n);printf(InputerrorsorDataoverflow!!!pleasere-enter\n\n);fflush(stdin);/*清除缓存*/}（6）主函数voidmain()/*主函数*/{intg[max][max],n;priline(linelenght);n=adjg(g);priline(linelenght);priline(linelenght);printf(Inputtheadjacencymatrixwithoutdirectedgraph:\n);pri(g,n);printf(\n);printf(Minim