数据结构(最小生成树普利姆算法).doc

.:......一、问题分析和任务定义在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的最小生成树。问题的输入数据的格式为:首先提示输入带权网络的顶点边数,我定义的为整形数据型,然后输入每一条边的信息,即边的两个顶点以及权值,是十进制整数类型,这样我们就建立一个带权网络,并用邻接矩阵来存储,生成一个方阵显示出来。问题的输出数据格式为:输出是以邻接矩阵存储结构下的方阵,以及从不同顶点开始省城的最小生成树。题目要求以及达到目标:题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树,并且输出各边的权值。..三、测试数据第一组顶点数(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 预测结果<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}(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的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中,边上权值之和最小的生成树,另外最小生成树也可能是多个,他们之间的权值之和相等。..五、模块划分(1)预处理#include<>#include<>#defineinf9999#definemax40#definelinelenght77(2)普里姆算法voidprim(intg[][max],intn)/*prim的函数*/{intlowcost[max],closest[max];inti,j,k,min;for(i=2;i<=n;i++)/*n个顶点,n-1条边*/{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++)/*寻找满足边的一个顶点在U,另一个顶点在V的最小边*/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]){lowcost[j]=g[k][j];closest[j]=k;}printf("\n");