4最小生成树.doc

第四题::最小生成树问题问题描述:若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络,是一个网的最小生成树问题。基本要求:(1)利用克鲁斯卡尔算法求网的最小生成树;(2)实现抽象数据类型定义MFset。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中个挑边以及他们的权值。,拟将整体程序分为三大模块。以下是三个模块的大体分析:(1)通信线路一旦建立,必然是双向的。因此,构造生成树的网一定是无向的,设图的顶点个数不超过30个,并为就简单起见,网中边的权值设成小于100的整数,可利用c语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应。(2)为了便于选择权值最小边,此题的存储结构不应选择邻接矩阵的数组表示法,也不选取邻接表,而是以存储边(带权)的数组表示图。{数据对象V:V是具有相同特征的数据元素的集合,成为顶点集数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v,w之间存在路径}基本操作P:seeks(intset[],intv)初始条件:v存在操作结果:返回顶点数据kruskal(edgesetge[],intn,inte)初始条件:图ge存在操作结果:算出图之间的最短路径}#include""#include""#include""#defineMAXE100typedefstructedges{intbv;inttv;intw;}edgeset;intseeks(intset[],intv){inti;i=v;while(set[i]>0)i=set[i];returni;}voidkruskal(edgesetge[],intn,inte){intset[MAXE],v1,v2,i,j;for(i=1;i<n+1;i++)set[i]=0;i=1;j=1;while(j<=e&&i<=n-1){v1=seeks(set,ge[j].bv);v2=seeks(set,ge[j].tv);if(v1!=v2){printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);set[v1]=v2;i++;}j++;}}voidinsertsort(edgesetge[],inte){inti,j;for(i=2;i<=e;i++)if(ge[i].w<ge[i-1].w){ge[0]=ge[i];j=i-1;while(ge[0].w<ge[j].w){ge[j+1]=ge[j];j--;}ge[j+1]=ge[0];}}intmain(){printf("\t\t************************************\n\n");printf("\t\t最小生成树问题:\n\n");printf("\t\t************************************\n\n");srand((unsigned)time(0));edgesetge[MAXE];intN,i,r,e;printf("请输入顶点个数:");