普里姆算法生成最小生成树课程设计报告书

1、0 / 32数据结构（C 语言描述） 课程设计学院计算机工程学院 班 级12 级软件技术 1 班 学 号22、120 124、133、121 学生周鑫、王彬彬、松平 圣玮、远迎 指导教师 余云霞 JINGCHU UNIVERSITY OF TECHNOLOGY1 / 322014年1月 3 日2 / 32目目 录录1 1 课程设计介绍课程设计介绍 1 11.1 课程设计容 11.2 课程设计要求 12 2 课程设计原理课程设计原理 2 22.1 课设题目粗略分析 22.2 原理图介绍 32.2.1 功能模块图 32.2.2 流程图分析 33 3 数据结构分析数据结构分析 10103.1 存储结

2、构 103.2 算法描述 124 4 调试与分析调试与分析 22224.1 调试过程 224.2 程序执行过程 22参考文献参考文献 2 28 8附录附录 2 28 80 / 321 1 课程设计介绍课程设计介绍1.11.1 课程设计容课程设计容 编写算法能够建立带权图，并能够用 Prim 算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.21.2 课程设计要求课程设计要求1. 可以输入顶点、边数与各路径的权值；2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表；3. 可以输出建立的最小生成树；4. 画出流程图，且函数有必要说明

3、、注释；5. 课设完成后上交报告与核心代码。1 / 322 2 课程设计原理课程设计原理2.12.1 课设题目粗略分析课设题目粗略分析根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：1. 创建网图并确定网图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构，方便以后的编程。2.Prim 算法。设置两个新的集合 U 和 T，其中 U 用于存放带权图 G的最小生成树的结点的集合，T 用于存放带权图 G 的最小生成树边的权值的集合。其思想是：令集合 U 的初值为 Uu0（即假设构造最小生成树时从结点 u

4、0 开始） ，集合 T 的初值为 T=。从所有结点 u 属于 U 和结点 v 属于 V 但不属于 U 的带权边中选出具有最小权值的边（u，v） ，将结点 v 加入集合 U 中，将边（u，v）加入集合 T 中。如此不断重复，当 U=V 时，最小生成树便构造完毕。2 / 322.22.2 原理图介绍原理图介绍2.2.12.2.1 功能模块图功能模块图显示菜单进行选择选择创建（有）无向图与存储方式有向图邻接矩阵无向图邻接矩阵有向图邻接表无向图邻接表调用普里姆算法输出最小生成树结束开始图 2.1 功能模块图2.2.22.2.2 流程图分析流程图分析1. 主函数3 / 32开始开始显示菜单，选择输入 1

5、 或 2选择 1选择 2 调用 createAgraph()函数结束结束选择 1调用 CreateGraph()函数选择 2调用 CreateMGraph()函数调用 createALgraph()函数调用 Prim 函数，输出最小生成树 图 2.2 主函数流程图2. CreateMGraph()函数4 / 32开始开始int i,j,kfor(i=0;in;i+)scanf(“n%c”,&(G-vexsi);for(i=0;in;i+)for(j=0;in;i+)i=jG-edgesij=0;YNG-edgesij=max;for (k=0;ke;k+)scanf(n%d,%d,%d

6、,&i,&j,&weight);G-edgesij=weight;OutPut(G);prim(G-edges,G-n,G-vexs); 图 2.3 CreateMGraph()函数流程图结束结束5 / 323Prim()函数开始开始int i,j,k,lowcost100,mincost;for(i=1;in;i+) lowcosti=gm0i;closevertexi=0; seti=0; i=1; j=1;YYlowcost0=0;closevertex0=0;for(i=1;in;i+)mincost=max;j=1;k=1;jnlowcostjmincost&

7、amp;lowcostj!=0mincost=lowcostj;k=j;j+;NNprintf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0;6 / 32for(j=0;jn;j+)gmkjn),&(g-e);for(i=0;in;i+)scanf(%d,&(g-adjlisti.vertex);g-adjlisti.firstedges=NULL;for(k=0;ke;k+)scanf(%d,%d,%d,&i,&j,&w);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=j

8、;s-weight=w;s-next=g-adjlisti.firstedges;g-adjlisti.firstedges=s;8 / 325.邻接矩阵 Output()输出函数开始开始int i,j;for (i=0;in;i+) printf(%d ,G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)printf(t%d ,G-edgesij);结束结束图 2.6 Output()函数流程图9 / 323 3 数据结构分析数据结构分析3.13.1 存储结构存储结构定义邻接矩阵与邻接表的结构体（1）邻接矩阵#define MaxVertexNum 100#defin

9、e max 1000typedef int VertexType;typedef int EdgeType;typedef struct VertexType vexsMaxVertexNum; EdgeType edgesMaxVertexNumMaxVertexNum; int n,e; MGraph;（2）邻接表#defineMaxVertexNum 100typedef int vertextype;typedef struct node int adjvex;10 / 32int weight; struct node *next; edgenode;typedef struct v

10、node vertextype vertex; edgenode *firstedges; vertexnode;typedef vertexnode AdjListMaxVertexNum;typedef struct AdjList adjlist; int n,e;ALgraph;(3)邻接表转换成邻接矩阵辅助结构体typedef intedgetype ;typedef struct edgetype vexsMaxVertexNum; edgetype edgesMaxVertexNumMaxVertexNum; int n,e; graph; /*邻接表转换成邻接矩阵辅助结构体*/

11、11 / 323.23.2 算法描述算法描述1. 创建有向网图邻接矩阵存储void CreateMGraph(MGraph *G) int i,j,k,weight; printf(t=有向网图邻接矩阵=n);printf(请输入顶点数和边数：); scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) if(i=j) G-edgesij=0; else G-edgesij=max; /*初始化邻接

12、矩阵*/ printf(输入边对应的两个顶点的序号与权值：); for (k=0;ke;k+) scanf(n%d,%d,%d,&i,&j,&weight); G-edgesij=weight;12 / 32 printf(输出顶点信息与邻接矩阵:n ); OutPut(G); printf(输出最小生成树的信息:n); prim(G-edges,G-n,G-vexs);2. 创建无向网图邻接矩阵存储void CreateGraph(MGraph *G) int i,j,k,weight; printf(t=无向网图邻接矩阵=n); printf(请输入顶点数和边数：)

13、; scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) if(i=j) G-edgesij=0; else G-edgesij=max; /*初始化邻接矩阵*/13 / 32 printf(输入边对应的两个顶点的序号与权值：); for (k=0;ke;k+)scanf(n%d,%d,%d,&i,&j,&weight); G-edgesij=weight; G-edges

14、ji=weight; printf(输出顶点信息与邻接矩阵:n ); OutPut(G); printf(输出最小生成树的信息:n); prim(G-edges,G-n,G-vexs); 3. 创建有向网图邻接表存储void createAgraph( ALgraph *g) /*创建有向网图*/ int i,j,k,w; edgenode *s; printf(t=有向网图邻接表=n); printf(输入顶点数和边数:); scanf(%d,%d%*c,&(g-n),&(g-e); printf(n 输入顶点:); for(i=0;in;i+)14 / 32 scanf(%

15、d,&(g-adjlisti.vertex); g-adjlisti.firstedges=NULL; printf(n 输入边和权值:); for(k=0;ke;k+) scanf(%d,%d,%d,&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-weight=w; s-next=g-adjlisti.firstedges; g-adjlisti.firstedges=s; DispAdjList(g);4. 创建无向网图邻接表存储void createALgraph(ALgraph

16、 *g) /*创建无向网图*/ int i,j,k,w; edgenode *s;printf(t=无向网图邻接表=n);15 / 32 printf(输入顶点数和边数:); scanf(%d,%d%*c,&(g-n),&(g-e); printf(n 输入顶点:); for(i=0;in;i+) scanf(%d,&(g-adjlisti.vertex); g-adjlisti.firstedges=NULL; printf(n 输入边和权值:); for(k=0;ke;k+) scanf(%d,%d,%d,&i,&j,&w); s=(edge

17、node*)malloc(sizeof(edgenode); s-adjvex=j; s-weight=w; s-next=g-adjlisti.firstedges; g-adjlisti.firstedges=s; s=(edgenode*)malloc(sizeof(edgenode); s-adjvex=i; s-weight=w; s-next=g-adjlistj.firstedges; g-adjlistj.firstedges=s;16 / 32 DispAdjList(g);5.prim 算法void prim(int gmMaxVertexNum ,int n,int cl

18、osevertex ) /*普里姆算法*/ int lowcost100; int mincost; int i,j,k; for(i=0;in;i+) lowcosti=gm0i; closevertexi=0; lowcost0=0; closevertex0=0; for(i=1;in;i+) mincost=max; j=1;17 / 32 k=1; while(jn) if(lowcostjmincost&lowcostj!=0) mincost=lowcostj; k=j; j+; printf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=

19、0; for(j=0;jn;j+) if(gmkjlowcostj) lowcostj=gmkj; closevertexj=k; 18 / 326. 输出邻接矩阵存储函数void OutPut (MGraph *G) int i,j; printf(tE= ); for (i=0;in;i+) printf(%d ,G-vexsi); printf(); printf(n); for(i=0;in;i+) for(j=0;jn;j+) printf(t%d ,G-edgesij); printf(n); 7.输出邻接表存储函数void DispAdjList(ALgraph *g) int

20、i; edgenode *p;19 / 32 printf(n 网图的邻接表表示如下：n); for (i=0; in; i+) printf(%d,%3d=,i,g-adjlisti.vertex); p=g-adjlisti.firstedges; while (p!=NULL) printf(%d,%d)-,p-adjvex,p-weight); p=p-next; printf(n); 8.邻接表转换成邻接矩阵函数void change(ALgraph *g) /*邻接表转换成邻接矩阵*/ int i,j; edgenode *p; graph *M;M=(graph*)malloc(

21、sizeof(graph); M-n=g-n; M-e=g-e;20 / 32 for(i=0;ie;i+) for(j=0;je;j+) if(i=j)M-edgesij=0; else M-edgesij=MaxVertexNum; for(i=0;in;i+) M-vexsi=g-adjlisti.vertex; for(i=0;in;i+) p=g-adjlisti.firstedges; while(p) M-edgesip-adjvex=p-weight; p=p-next; prim(M-edges,M-n,M-vexs);21 / 324 4 调试与分析调试与分析4.14.1

22、调试过程调试过程测试数据（对下图进行测试）：4.24.2 程序执行过程程序执行过程系统使用说明：1. 输入的数据可以是 100 以的整数；2. 本系统可以建立带权图，并能够用 Prim 算法求该网图的最小生成树。 3. 该系统会有菜单提示，进行选项：右图是 6 个顶点的 10 条边的连通图六个顶点分别是：1 2 3 4 5 6顶点序号和边上的权植分别是0 1 110 2 150 3 181 2 331 4 122 3 202 4 222 5 253 5 274 5 2912435622 / 324.程序实际运行截图（1）有向图邻接矩阵输出最小生成树截图：23 / 32（2）无向图邻接矩阵输出最小生成树截图：24 / 3225 / 32（3）有向图邻接表输出最小生成树截图：26 / 32（4）无向图邻接表输出最小生成树截图：27 / 32参考文献参考文献（1）素若， 数据结构（C 语言描述） ，200