最小生成树的应用数据结构课程设计.doc

摘 要求一个网的最小生成树，即以最低的经济建设n个城市之间的通信网，利用普里姆算法和克鲁斯卡尔算法求这个网的最小生成树。关键词：网的最小生成树；Kruskal算法；Prim算法；边和权值。目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分34 详细设计541数据类型的定义542主要模块的算法描述55 测试分析136 课程设计总结13参考文献16附录（源程序清单）1711 问题描述若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济建设这个通信网，是一个网的最小生成树。2 需求分析（1）.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。 对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。（2）.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。利用克鲁斯卡尔算法和普利姆算法实现。3 概要设计31抽象数据类型定义 1.ADT Graph 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR VR=v,w|v,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词p(v,w)定义了弧v,w的意义或信息 基本操作：(1) CreatGraph(G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。(2) LocateVex(G, u)； 初始条件：图G存在,u和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。(3) DestoryGraph(u)；初始条件：图G存在。操作结果：销毁图G。(4) GetVex(G, v)；初始条件：图G存在，v是图中某个顶点。操作结果：返回v的值。(5) NextAdjVex(G, v, w)；初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。(6) BFSTraverse(G, Visit( )；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit( )失败，则操作失败。2. 存储结构Typedef struct int adj; int weight;AdjMatrixMAXMAX;Typedef struct djMatrix arc; int vexnum, arcnum; MGraph;32模块划分本程序包括五个模块：（1）主函数模块 (2) 邻接矩阵定义模块代码typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs;int vexnum,arcnum;MGraph_L;int localvex(MGraph_L G,char v) int i=0; while(G.vexsi!=v) +i; return i;(3) 创建链接矩阵模块代码 int creatMGraph_L(MGraph_L G) char v1,v2; int i,j,w; cout创建无向图（城市分布图）endl;cout 请输入图G顶点（城市）和弧（边）的个数:(4 6)不包括“()”endl; cinG.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点（城市）iendl; cinG.vexsi; for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括“()”endl; cinv1v2w; i=localvex(G,v1); j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.vexnum;(4)最小生成树Prim算法及代价模块代码 (5)最小生成树kruskal算法及代价模块代码4 详细设计41数据类型的定义（1）树类型#define MAXVALUE 100#define MAXLEAF 50#define MAXNODE MAXLEAF*2-1;（2）图类型typedef struct node int adjvex; int w; struct node *nextedge; edgenode; typedef struct char data; int id; edgenode *firstedge; vexnode; 42主要模块的算法描述（1）主函数algraph gra; MGraph_L G; int i,d,g2020;char a=a; d=creatMGraph_L(G); vnode v;coutendl注意：若该图为非强连通图(含有多个连通分量)时endl最小生成树不存在,则显示为非法值endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、最小生成树PRIM算法及代价endl;int s; char y=y;while(y=y) cout请选择菜单：endl; cins;switch(s)case 0: cout邻接矩阵显示如下：endl; ljjzprint(G); break;case 1: for(i=0;i!=G.vexnum;+i) for(intj=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutprim:endl; prim(g,d); break; coutendl是否继续？y/n:; ciny; if(y=n) break; 2、用prim算法求解最小生成树3、用kruskal算法最最小生成树功能选择开 始1、建立邻接矩阵结 束图4.1 流程图（2）最小生成树Prim算法及代价模块代码int prim(int gmax,int n) int lowcostmax,prevexmax; int i,j,k,min;int sum=o; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)(lowcostj!=0)min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min; lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) lowcostj=gkj; prevexj=k; printf(n); cout最少生成树的代价:; coutsum; return 0;开 始输入ch, 用于判断是否创建无向网ch=Y1 调用create()函数flag=02调用display()函数st=03调用prim ()函数4调用Minium ()函数 否 是 否 是输入起点st 是 否结 束图4.2 Prim算法流程图(3) 最小生成树kruskal算法及代价模块代码void MiniSpanTree(MGraphA *D)/生成最小生成树 int i, j, n, m, SUM=0; int k = 1;int parentM; edge edgesM;for ( i = 1; i D-vexnum; i+) for (j = i + 1; j = D-vexnum; j+) if (D-arcij.adj = 1) edgesk.begin = i; edgesk.end = j;edgesk.weight = D-arcij.weight; k+; sort(edges, D);for (i = 1; i = D-arcnum; i+) parenti = 0; printf(最小生成树为:n);for (i = 1; i = D-arcnum; i+)/核心部分 n = Find(parent, edgesi.begin); m = Find(parent, edgesi.end);if (n != m) parentn = m; printf( %d, %d %dn, edgesi.begin, edgesi.end, edgesi.weight);SUM=SUM+edgesi.weight;开始int setMAXE,v1,v2,i,j;for(i=1;in+1;i+)seti=0; i=1; j=1;j=ei=n-1v1!=v2v1=seeks(set,gej.bv);v2=seeks(set,gej.tv);printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;YY结束NN图4.3 Kruskal算法流程图5 测试分析测试数据及结果如下：图5.1 创建邻接矩阵图5.2 Prim算法求解图5.3 Kruskal算法求解6 课程设计总结从这次给我的课程设计任务中我深刻地体会到了编程并非易事。任何事情并不是想我们想的那样简单和容易。只有扎扎时时的学习知识才能解决实际生活中的实际问题。从这次课设中也让我明白以后要多了解相关知识,更多的做一些实践动手活动，将知识运用到实际问题中。同时，增加自己的动手能力，这样才能便于我们更好的解决问题。为今后打下好的基础。实验过程中，我遇到了很多问题，一开始就要建一个图，然后利用kruskal算法解决问题，这个题目是一个十分联系实际的题目，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。过而能改，善莫大焉。在课程设计过程中，我不断发现错误，不断改正，不断领悟，不断获取。最终的调试运行环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于迎刃而解。当我完成课程设计后,我感到很欣喜。能完成让我感到什么叫做编程的快乐,什么叫做乐趣。也让明白要想把通信工程这门专业学好必须持之以恒地努力下去。附录（源程序清单）#include iostream#include malloc.husing namespace std; #define int_max 10000#define inf 9999 #define max 20#define MAX 20#define M 20typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20;AdjMatrix arcs; int vexnum,arcnum;MGraph;int localvex(MGraph G,char v) int i=0; while(G.vexsi!=v) +i; return i;void ljjzprint(MGraph G) int i,j,n=0; printf(建立的邻接矩阵如下：n); printf(n); printf( _n); for(i=0;i!=G.vexnum;i+) for(j=0;j!=G.vexnum;j+) if(j=0)printf( ); printf(%d,G.arcsij.adj);printf( );n+; if(n=G.vexnum) printf(n);n=0; printf( _n);int creatMGraph(MGraph G)char v1,v2; int i,j,w; printf(建立邻接矩阵:n); printf(请输入图G顶点（城市）和弧（边）的个数:); scanf(%d,G.vexnum); scanf(%d,G.arcnum); printf(输入所有顶点:); for(i=0;iG.vexnum;+i) cinG.vexsi; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=int_max; G.=NULL; printf(输入所有边及依附的顶点（城市）和权（距离）:n);for(int k=0;kG.arcnum;k+) cinv1v2w; i=localvex(G,v1); j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; ljjzprint(G); printf(图G邻接矩阵创建成功！n); return G.vexnum; int visitedmax; int we;typedef struct arcnode int adjvex; struct arcnode *nextarc; char *info; arcnode;typedef struct vnode char data; arcnode *firstarc; vnode,adjlist;typedef struct/图的定义 adjlist verticesmax; int vexnum, arcnum; int kind; algraph;int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax, prevexmax; int i,j,k,min; int sum=0; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min;lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) lowcostj=gkj;prevexj=k; printf(n); cout最少生成树的代价:; coutsum; return 0; typedef struct int begin; int end; int weight; edge;typedef struct int adj; int weight; AdjMAXMAX;typedef struct Adj arc; int vexnum, arcnum; MGraphA;void CreatGraph(MGraphA *);/函数申明void sort(edge* ,MGraphA *);void MiniSpanTree(MGraphA *);int Find(int *, int );void Swapn(edge *, int, int);void CreatGraph(MGraphA *D)/构件图int i, j,n, m;printf(请输入边数和顶点数:);scanf(%d %d,D-arcnum,D-vexnum);for (i = 1; i = D-vexnum; i+)/初始化图for ( j = 1; j = D-vexnum; j+) D-arcij.adj = D-arcji.adj = 0;for ( i = 1; i = D-arcnum; i+)/输入边和权值printf(n请输入有边的2个顶点); scanf(%d %d,n,m);while(n 0 | n D-vexnum | m 0 | n D-vexnum)printf(输入的数字不符合要求 请重新输入:); scanf(%d%d,n,m); D-arcnm.adj = D-arcmn.adj = 1; getchar();printf(n请输入%d与%d之间的权值:, n, m); scanf(%d,D-arcnm.weight);printf(邻接矩阵为:n);for ( i = 1; i = D-vexnum; i+)for ( j = 1; j = D-vexnum; j+)printf(%d ,D-arcij.adj); printf(n);void sort(edge edges,MGraphA *D)/对权值进行排序int i, j;for ( i = 1; i D-arcnum; i+)for ( j = i + 1; j = D-arcnum; j+)if (edgesi.weight edgesj.weight) Swapn(edges, i, j);printf(权排序之后的为:n);for (i = 1; i D-arcnum; i+)printf( %d, %d %dn, edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int j)/交换权值 以及头和尾int temp; temp = edgesi.begin;edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end;edgesi.end = edgesj.end; edgesj.end = temp;temp = edgesi.weight; edgesi.weight = edgesj.weight;edgesj.weight = temp;void MiniSpanTree(MGraphA *D)/生成最小生成树int i, j, n, m,SUM=0; int k = 1;int parentM; edge edgesM;for ( i = 1; i D-vexnum; i+)for (j = i + 1; j = D-vexnum; j+)if (D-arcij.adj = 1)edgesk.begin = i; edgesk.end = j; edgesk.weight = D-arcij.weight; k+; sort(edges, D);for (i = 1; i = D-arcnum; i+)parenti = 0; printf(最小生成树为:n);for (i = 1; i = D-arcnum; i+)/核心部分n = Find(parent, edgesi.begin); m = Find(paren