最小生成树问题 中北大学数据结构课程设计

中北大学数据结构与算法课程设计说明书学院、系：软件学院专业：软件工程班级：学生姓名：学号：设计题目：最小生成树问题起迄日期:2015年1月12日-2015年1月29日指导教师:王秀娟2015年1月29日11需求分析1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。1.4程序通过人机交互实现数据的输入和输出。2选题要求设计内容：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性。3程序设计方法及主要函数介绍ADTGraph{数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径}基本操作P;CreateMGraph(MGraph*G)初始条件：V是图的顶点集，VR是图的边的集合。操作结果：按V和VR的定义构造图G，用邻接矩阵存储。CreateALGraph(ALGraph*G)2初始条件：V是图的顶点集，VR是图的边的集合。操作结果：按V和VR的定义构造图G，用邻接表存储。LocateVex（G，u）初始条件：图G存在，u和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。MiniSpanTree_PRIM（G,u)初始条件：图G存在，u是图G中的一个顶点。操作结果：用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。Kriuskal(G)初始条件：图G存在操作结果：用克鲁斯卡尔算法构造图G的最小生成树T，输出T的各条边。ListToMat(MGraph*G1,ALGraph*G2)初始条件：图G2存在操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图G1表示。MatToList(MGraph*G1,ALGraph*G2)初始条件：图G1存在操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图G2表示。LocateVex(MGraph*G,VertexTypeu)初始条件：图G存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1}ADTGraph4程序源代码（包括注释）#includestdio.h#includestring.h#includemalloc.h#defineOK1#defineERROR0#defineTURE1#defineFALSE0#defineOVERFLOW-13#defineINFEASIBLE-2typedefintStatus;#defineINFINITY0#defineMAX_VERTEX_NUM20#defineMAX_NAME5typedefcharVertexType[MAX_NAME];typedefintVRType;typedefstructArcCell{VRTypeadj;/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*//*对带权全图，则为权值类型*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstructMGraph{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/}MGraph;/*以下定义邻接表类型*/typedefstructANode/*弧的结点结构类型*/{intend;intbegin;/*该弧的终点位置*/intweight;/*该弧的相关信息,这里用于存放权值*/structANode*nextarc;/*指向下一条弧的指针*/}ANode;typedefstructVNode/*邻接表头结点的类型*/4{VertexTypevertex;/*顶点信息*/intbianhao;ANode*firstarc;/*指向第一条弧*/}VNode,AdjList[MAX_VERTEX_NUM];/*AdjList是邻接表类型*/typedefstructALGraph{AdjListadjlist;/*邻接表*/intvexnum,arcnum;/*图中顶点数n和边数e*/}ALGraph;/*图的邻接表类型*/intLocateVex(MGraph*G,VertexTypeu){/*初始条件：图G存在，u和G中顶点有相同特征*//*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/inti;for(i=0;iG-vexnum;++i)if(strcmp(u,G-vexs[i])==0)returni;return-1;}图一/*建立无向图的邻接表算法*/StatusInitALGraph(ALGraph*G){5inti;printf(请输入城市的数量及城市间的路径数目\n);scanf(%d%d,&G-vexnum,&G-arcnum);for(i=0;iG-vexnum;i++){/*建立顶点表*/printf(请输入第%d个城市的名称\n,i);scanf(%s,&G-adjlist[i].vertex);/*读入顶点信息*/G-adjlist[i].firstarc=NULL;/*边表置为空表*/G-adjlist[i].bianhao=i;}printf(每个城市所对应的序号为\n);for(i=0;iG-vexnum;i++){printf(序号：%d---城市：%s\n,G-adjlist[i].bianhao,&G-adjlist[i].vertex);//注意此处的&}returnOK;}StatusPrintALGraph(ALGraph*G){inti,end,begin,weight;ANode*s;for(i=0;iG-vexnum;i++){/*建立顶点表*/printf(%s------,&G-adjlist[i].vertex);s=G-adjlist[i].firstarc;while(s!=NULL){printf((%s,%s):%d,&G-adjlist[s-end].vertex,&G-adjlist[s-begin].vertex,s-weight);s=s-nextarc;6}printf(\n);}returnOK;}voidCreateALGraph(ALGraph*G){inti,j,k,weight;ANode*s;InitALGraph(G);for(k=0;kG-arcnum;k++){/*建立边表*/printf(\n请输入第%d条边的两个城市的编号及路径的架设费用:,k);scanf(%d,&i);scanf(%d,&j);scanf(%d,&weight);/*读入边(vi，vj)的顶点对序号*/s=(ANode*)malloc(sizeof(ANode));/*生成边表结点*/if(!s){printf(申请空间失败!\n);exit(OVERFLOW);}s-begin=j;/*邻接点序号为j*/s-end=i;s-weight=weight;s-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=s;/*将新结点*s插入顶点vi的边表头部*/s=(ANode*)malloc(sizeof(ANode));if(!s){printf(申请空间失败!\n);7exit(OVERFLOW);}s-begin=i;/*邻接点序号为i*/s-end=j;s-weight=weight;s-nextarc=G-adjlist[j].firstarc;G-adjlist[j].firstarc=s;/*将新结点*s插入顶点vj的边表头部*/}PrintALGraph(G);}/*CreateALGraph*/StatusPrintMGraph(MGraph*G){inta;inti,j;printf(邻接矩阵表示法为：\n);printf(\t);for(i=0;iG-vexnum;++i)printf(\t%5s,&G-vexs[i]);printf(\n);for(i=0;iG-vexnum;i++){printf(\t%5s,&G-vexs[i]);for(j=0;jG-vexnum;j++){printf(\t%5d,G-arcs[i][j].adj);}printf(\n);}returnOK;}8图二StatusInitMGraph(MGraph*G){inti,j;printf(请输入城市的数量及城市间的路径数目：\n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(\n请依次输入城市的名称，字符串类型\n);for(i=0;iG-vexnum;++i){/*构造顶点向量*/scanf(%s,&G-vexs[i]);}for(i=0;iG-vexnum;++i)/*初始化邻接矩阵*/for(j=0;jG-vexnum;++j)G-arcs[i][j].adj=INFINITY;returnOK;}StatusCreateMGraph(MGraph*G){/*采用数组（邻接矩阵）表示法，构造无向网G*/9inti,j,k,weight,IncInfo;VertexTypeva,vb;InitMGraph(G);for(k=0;kG-arcnum;++k){printf(请输入第%d条路径的起点城市和终点城市的名称及路径的架设费用\n,k);scanf(%s%s%d,&va,&vb,&weight);i=LocateVex(G,va);j=LocateVex(G,vb);G-arcs[i][j].adj=weight;G-arcs[j][i].adj=weight;}PrintMGraph(G);returnOK;}typedefstructMINSIZE{//记录从顶点集U到V-U的代价最小的边的辅助数组定义*VertexTypeadjvex;VRTypelowcost;}minside[MAX_VERTEX_NUM];Statusmininum(minsideclosedge,MGraph*G){/*求closedege,lowcost的最小正值*/inti=0,j,k,min;while(!closedge[i].lowcost)i++;min=closedge[i].lowcost;k=i;for(j=i+1;jG-vexnum;j++)if(closedge[j].lowcost0)if(minclosedge[j].lowcost){10min=closedge[j].lowcost;k=j;}returnk;}图三voidMiniSpanTree_PRIM(MGraph*G,VertexTypeu){/*用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边*/inti,j,k;intqidian,zhongdian,weight;VertexTypeva,vb;minsideclosedge;k=LocateVex(G,u);for(j=0;jG-vexn