数据结构课程设计求最小生成树

1、#大学数据结构课程设计报告题目： 图的最小生成树 院（系）： 学生姓名: 班级： 学号:起迄日期: 指导教师: 指导教师评语： 成绩： 签名： 年 月 日20112012年度 第 2 学期一、需求分析1.问题描述： 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 该题目需要运用最小生成树来解决。最小生成树的代价之和最小，所以是一种最经济的架设方法。2.基本功能 该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。 3.输入输出 首先输入顶点的个数以及边的个数，格式如:4 6。然后输

2、入边的权值，格式如：a b 1。输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。最小生成树的格式为：权值。二、 概要设计1.设计思路： 问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。 2.数据结构设计：1.抽象数据类型如下：ADT Grap

3、h 数据对象 V：v是具有相同特征的数据元素的集合，称为顶点集。 数据关系 R：R=VR VR=|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧的意义或信息基本操作：1) GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作条件：按V和VR的定义构造图G。 2）LocateVex（G,u）； 初始条件：图G存在，u和G中顶点有相同的特征。 操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。 2.存储结构 typedef struct ArcCell int adj; char *info;ArcCell,AdjM

4、atrix2020;typedef struct char vexs20;/定义一个顶点数组 AdjMatrix arcs; int vexnum,arcnum;MGraph_L; typedef struct arcnode/弧结点 int adjvex;/该弧指向的顶点的位置 struct arcnode *nextarc;/弧尾相同的下一条弧 char *info;/该弧信息arcnode;typedef struct vnode/邻接链表顶点头接点 char data;/结点信息 arcnode *firstarc;/指向第一条依附该结点的弧的指针vnode,adjlist;3.软件结

5、构设计：开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3. PRIM算法4.kruscal算法结束三、 详细设计 1主函数和其他函数的伪码算法 主函数： void main() algraph gra; MGraph_L G; int i,j,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); cout*endl; cout*1。用邻接矩阵存储：*endl; cout*2。用邻接表存储：*endl; cout*3。PRIM算法求最经济的架设方法*endl; cout*4。KRUSCAL算法最经济的架设方法*endl; cout*

6、endlendl; int s; char y=y; while(y=y) cout请选择菜单：s; switch(s) case 1: cout用邻接矩阵存储为：endl; ljjzprint(G); break; case 2: cout用邻接表存储为：endl; adjprint(gra); break; case 3: for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutPRIM算法最经济的架设方法为:endl; prim(g,d); break; case 4: coutkruscal算法

7、最经济的架设方法为:endl; kruscal_arc(G,gra); break; coutendly; if(y=n) break; 邻接表的输出：void adjprint(algraph gra)/输出邻接表 int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; 邻接矩阵的输出：void ljjzprint(MGraph_L G)/输出邻接矩阵 int i,j; for(i=0;i!=

8、G.vexnum;+i) for(j=0;j!=G.vexnum;+j) if(G.arcsij.adj=10000) cout0 ;elsecoutG.arcsij.adj ;coutendl; 创建图并以邻接矩阵表示：int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示 char v1,v2; int i,j,w; cout请输入城市数（顶点个数）和总道路的个数（弧的个数）:G.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入城市名i+1G.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0

9、;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.=NULL; for(int k=0;k!=G.arcnum;+k) cout请输入两城市间的距离（权）:v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout*endl; cout图创建成功endl; cout请根据如下进行操作endl; return G.vexnum;最小生成树kruscal算法：void kruscal_a

10、rc(MGraph_L G,algraph gra)/最小生成树kruscal算法 edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(

11、i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; 返回V的位置：int localvex(MGraph_L G,char v)/返回V的位置 int i=0; while(G.vexsi!=v) +i; return i;最小生成树PR

12、IM算法：int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U

13、,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;int find(int acrvisited,int f) while(acrvisitedf0) f=acrvisitedf; return f;3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示

14、。Main()函数:开始creatMGraph_L()creatadj()Switch（）ljjzprint()adjprint()prim()kruscal_arc()结束Adjprint（）函数：开始Int ii!=gra.vexnum输出ip!=NULLp-adjvexp=p-nextarc结束ljjzprint()函数：开始int i,ji!=G.vexnumj!=G.vexnum输出G.arcsij.adj结束creatMGraph_L（）函数：开始输入顶点和弧的个数输入顶点输入权确定顶点在图中的位置结束creatadj()函数：开始生成表i=vexnum?建立邻接表设置表头结点为空

15、循环生成其他结点，直到输入的邻接点为零生成空的表头结点做vexnum次循环生成其他结点，直道遇到空指针为止结束prim()函数：开始标志顶点1加入U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k加入U修改由顶点k到其他顶点边的权值结束得到最小生成树kruscal_arc()函数：开始确定弧的结点，以及弧的权比较弧的权的大小并对权小的赋值确定结点的位置结束不能生成环？ localvex()函数：开始i=0G.vexsi!=v+i返回V的位置结束4. 画出函数之间的调用关系图。Main（）creatMGraph_L()creatadj()prim()kruscal

16、_arc()ljjzprint()adjprint()localvex()find()四、 调试分析 1.实际完成的情况说明 程序完成了用prim和kruscal求一个图的最小生成树，并对图以邻接表与邻接矩阵的形式进行存储2.程序的性能分析 本程序操作简单，方便，能较好较快的完成最小生成树的求解，以及日常生活中，道路的优化，航线的优化，使用性能比较强。3.上机过程中出现的问题及其解决方案 1）数据之间类型不同，引发数据间交换紊乱。指针空间未分配而导致系统随机给出个错误数据。地址相冲突导致的程序错误。这些都没有语法错误但是在调试中将引起乱码，是个重要问题，而且会频繁出现。经过多次调试，然后解决了

17、这个问题。 2）在寻找下一结点时，寻找到最小权值边，将其两端的顶点信息及变的权值存储到辅助数组中。在设计解决这些问题的时候用多个for进行循环嵌套实现查找，判断。尤其是prim算法。 3）一些小细节尤其是要注意的。尤其是变量的定义，以及定义的位置。4.程序中可以改进的地方说明 本程序没有添加判断这个内容，对于一些没有最小生成树的图，没有判断功能。还有就是进行完一个图的运算就要关闭程序，重新再输入新的图。无法对多个图进行运算。5.程序中可以扩充的功能及设计实现假想。 程序能还可以添加上深度优先遍历和广度优先遍历，那么功能将会更好。五、 测试结果 数据的正确输入： 程序执行菜单： 邻接矩阵存储：邻

18、接表存储：Prim算法：Kruscal算法： 六、用户手册 1）顶点和弧的输入格式为：数字 数字 2）权值的输入格式为：城市名 城市名 权值 3）然后根据菜单提示完成操作七、体会与自我评价 数据结构课程设计结束了，可以说我收获了不少东西。我选择的题目是最小生成树的的问题，这个问题看似简单，但是做起来才发现自己的不足。一切事情都必须是亲手去做，才能发现里面的东西。我想之所以要有课程设计这门考试，就是让我们认识到眼高手低这个问题，然后固定一学期以来所学的知识。在课程设计过程中，我遇到了不少问题，问同学，查资料，虽然麻烦一点，但是得到结果后发现原来这个过程是很美的 。课程设计不得不说是对我们的一个历

19、练。让我们对知识认识的更加全面，把握的更加牢固。刚开始学习离散数学的时候，我觉得那并没有什么用处，但是后来学了数据结构，才发觉他们是紧密相连的。知识总是有一个连接点的，所以如果想提高，必须把所以的知识紧密结合。数据结构，给我们的编程提供了很多算法，这对我们以后的发展尤其重要。学好这么课是必须的。可以说，我们现在就是一个装了一半水的瓶子，无法平衡一些东西，遇到问题也会有些波澜，对于充实自己，这非常的有必要。让自己稳下来，静下来，吸纳知识，充实自己。平庸之人就得多问，在问问题中认识到自己。落后之人就得多做，在实践中提高自己。我想，这次课程设计，我不但收获的是知道，更多的是认识自己。只有更好的认识自

20、己，以后的路才可以走的更顺一些。不能说，没有什么坎坷，至少遇到坎坷会随机应变，会越过它。最后，我要说的是，我会努力，把落下的东西都捡起。我会时刻提醒自己，数据结构对于计算机专业有多么的重要。在以后的程序中，多用，多练，把各种算法了然于胸，虽然做到炉火纯青有些难，但是也要做到驾轻就熟。源代码#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCell int adj; char *info;ArcCell,AdjMat

21、rix2020;typedef struct char vexs20;/定义一个顶点数组 AdjMatrix arcs; int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置 int i=0; while(G.vexsi!=v) +i; return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示 char v1,v2; int i,j,w; cout请输入城市数（顶点个数）和总道路的个数（弧的个数）:G.vexnumG.arcnum; for(i=0;i!=G.vexnum

22、;+i) cout输入城市名i+1G.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请输入两城市间的距离（权）:v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout*endl; cout图创建成功endl; cout请根据

23、如下进行操作endl; return G.vexnum;void ljjzprint(MGraph_L G)/输出邻接矩阵 int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) if(G.arcsij.adj=10000) cout0 ;elsecoutG.arcsij.adj ;coutadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)ma

24、lloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; return 1;void adjprint(a

25、lgraph gra)/输出邻接表 int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; typedef struct int adjvex; int lowcost; closedge;int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路

26、径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;void kruscal_arc(MGraph_L G,algraph gra)/最小生成树kruscal算法 edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; in