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

1、数据结构（c 语言描述） 课程设计学 院 计算机工程学院 班 级 12 级软件技术 1 班 学 号 2012304040122、120 124、133、121 学生姓名 周鑫、王彬彬、李松平 张圣玮、魏远迎 指导教师 余云霞 2014年 1月 3 日 jingchu university of technology目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.32.2.1 功能模块图.32.2.2 流程图分析.33 数据结构分析数据结构分析.103.1 存储结构.

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

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

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

5、始显示菜单，选择输入 1 或 2选择 1选择 2 调用 createagraph()函数结束结束选择 1调用 creategraph()函数选择 2调用 createmgraph()函数调用 createalgraph()函数调用 prim 函数，输出最小生成树 图 2.2 主函数流程图2. createmgraph()函数第 4 页 共 29 页开始开始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+)s

6、canf(n%d,%d,%d,&i,&j,&weight);g-edgesij=weight;output(g);prim(g-edges,g-n,g-vexs); 图 2.3 createmgraph()函数流程图结束结束第 5 页 共 29 页3prim()函数开始开始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;jnlowcostj

7、mincost&lowcostj!=0mincost=lowcostj;k=j;j+;nnprintf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0;第 6 页 共 29 页 for(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;s-weight

8、=w;s-next=g-adjlisti.firstedges;g-adjlisti.firstedges=s;第 8 页 共 29 页5. 邻接矩阵 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 页 共 29 页3 数据结构分析数据结构分析3.13.1 存储结构存储结构定义邻接矩阵及邻接表的结构体（1）邻接矩阵#define maxvertexnum 100#de

9、fine max 1000typedef int vertextype;typedef int edgetype;typedef struct vertextype vexsmaxvertexnum; edgetype edgesmaxvertexnummaxvertexnum; int n,e; mgraph;（2）邻接表#define maxvertexnum 100typedef int vertextype;typedef struct node int adjvex;第 10 页 共 29 页 int weight; struct node *next; edgenode;typed

10、ef struct vnode vertextype vertex; edgenode *firstedges; vertexnode;typedef vertexnode adjlistmaxvertexnum;typedef struct adjlist adjlist; int n,e;algraph;(3)邻接表转换成邻接矩阵辅助结构体typedef int edgetype ;typedef struct edgetype vexsmaxvertexnum; edgetype edgesmaxvertexnummaxvertexnum; int n,e; graph; /*邻接表转换

11、成邻接矩阵辅助结构体*/第 11 页 共 29 页3.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 页 共 29 页 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 页 共 29 页 printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;k+) scanf(n%d,%d,%d,&i,&j,&weight); g-edgesij=weight; g-edgesji=weight; printf

14、(输出顶点信息及邻接矩阵: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 页 共 29 页 scanf(%d,&(g-adjlisti.vert

15、ex); 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 *g) /*创建无向网图*/ int i,j,k,w; edgeno

16、de *s;printf(t=无向网图邻接表=n);第 15 页 共 29 页 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=(edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-weight=w

17、; 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 页 共 29 页 dispadjlist(g);5.prim 算法void prim(int gmmaxvertexnum ,int n,int closevertex ) /*普里姆算法*/ int lowcost100; int minco

18、st; 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 页 共 29 页 k=1; while(jn) if(lowcostjmincost&lowcostj!=0) mincost=lowcostj; k=j; j+; printf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0; for(j=0;jn;j+) if(gmkjlowcostj) lowcostj=g

19、mkj; closevertexj=k; 第 18 页 共 29 页6. 输出邻接矩阵存储函数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 i; edgenode *p;第 19 页 共 29 页 printf(n 网

20、图的邻接表表示如下：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(sizeof(graph); m-n=g-n; m-e=g-e;第

21、 20 页 共 29 页 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 页 共 29 页4 4 调试与分析调试与分析4.14.1 调试过程调试过程测试数据（对下图进行测试）

22、： 4.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 29124356第 22 页 共 29 页4.程序实际运行截图（1）有向图邻接矩阵输出最小生成树截图：第 23 页 共 29 页（2）无向图邻接矩阵输出最小生成树截图：第 24 页 共 29 页第 25 页 共 29 页（3）有向图邻接表输出最小生成树截图：第 26 页 共 29 页（4）无向图邻接表输出最小生成树截图：第 27 页 共 29 页参考文献参考文献（1）李素若， 数据结构（c 语言描述） ，2009，化学工业出版社 （2）严蔚敏、吴伟民， 数