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

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

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

3、流程图，且函数有必要说明、注释； 5. 课设完成后上交报告及核心代码。 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.22.2 原理图介绍原理图介绍 2.2.12.2.1 功能模块图功能模块图 显示菜单进行选择 选择创建（有）无向 图及存储方式 有向图邻接矩阵 无向图邻接矩阵 有向图邻接表 无向图邻接表 调用普里姆算法输出最小生成树 结束 开始 图 2.1 功能模块图 2.2.2 流程图分析流程图分析 1.

5、 主函数 开始开始 显示菜单，选 择输入 1 或 2 选择 1选择 2 调用 createagraph() 函数 结束结束 选择 1 调用 creategraph()函 数 选择 2 调用 createmgraph() 函数 调用 createalgraph() 函数 调用 prim 函数，输出 最小生成树 图 2.2 主函数流程图 2. createmgraph()函数 开始开始 int i,j,k for(i=0;in;i+) scanf(“n%c”, for(i=0;in;i+) for(j=0;in;i+) i=j g-edgesij=0; yn g-edgesij=max; for

6、(k=0;ke;k+) scanf(n%d,%d,%d, g-edgesij=weight; output(g); prim(g-edges,g-n,g-vexs); 图 2.3 createmgraph()函数流程图 结束结束 3prim()函数 开始开始 int i,j,k,lowcost100,mincost; for(i=1;in;i+) lowcosti=gm0i; closevertexi=0; seti=0; i=1; j=1; y y lowcost0=0; closevertex0=0; for(i=1;in;i+) mincost=max; j=1; k=1; jn low

7、costjmincost k=j; j+; n n printf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0; for(j=0;jn;j+) gmkjn), for(i=0;in;i+) scanf(%d, g-adjlisti.firstedges=null; for(k=0;ke;k+) scanf(%d,%d,%d, s=(edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-weight=w; s-next=g-adjlisti.firstedges; g-adjlisti.firstedges=s; 5

8、. 邻接矩阵 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()函数流程图 3 数据结构分析数据结构分析 3.13.1 存储结构存储结构 定义邻接矩阵及邻接表的结构体 （1）邻接矩阵 #define maxvertexnum 100 #define max 1000 typedef int vertextype; typedef int edgetype; typedef

9、struct vertextype vexsmaxvertexnum; edgetype edgesmaxvertexnummaxvertexnum; int n,e; mgraph; （2）邻接表 #define maxvertexnum 100 typedef int vertextype; typedef struct node int adjvex; int weight; struct node *next; edgenode; typedef struct vnode vertextype vertex; edgenode *firstedges; vertexnode; type

10、def vertexnode adjlistmaxvertexnum; typedef struct adjlist adjlist; int n,e; algraph; (3)邻接表转换成邻接矩阵辅助结构体 typedef int edgetype ; typedef struct edgetype vexsmaxvertexnum; edgetype edgesmaxvertexnummaxvertexnum; int n,e; graph; /*邻接表转换成邻接矩阵辅助结构体*/ 3.23.2 算法描述算法描述 1. 创建有向网图邻接矩阵存储 void createmgraph(mgra

11、ph *g) int i,j,k,weight; printf(t=有向网图邻接矩阵=n); printf(请输入顶点数和边数：); scanf(%d,%d, printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d, for (i=0;in;i+) for (j=0;jn;j+) if(i=j) g-edgesij=0; else g-edgesij=max; /*初始化邻接矩阵*/ printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;k+) scanf(n%d,%d,%d, g-edgesij=weight; printf(输出顶点信

12、息及邻接矩阵: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(请输入顶点数和边数：); scanf(%d,%d, printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d, for (i=0;in;i+) for (j=0;jn;j+) if(i=j) g-edgesij=0; else g-edgesij

13、=max; /*初始化邻接矩阵*/ printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;k+) scanf(n%d,%d,%d, g-edgesij=weight; g-edgesji=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);

14、 printf(输入顶点数和边数:); scanf(%d,%d%*c, printf(n 输入顶点:); for(i=0;in;i+) scanf(%d, g-adjlisti.firstedges=null; printf(n 输入边和权值:); for(k=0;ke;k+) scanf(%d,%d,%d, s=(edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-weight=w; s-next=g-adjlisti.firstedges; g-adjlisti.firstedges=s; dispadjlist(g); 4. 创建无向网图邻接

15、表存储 void createalgraph(algraph *g) /*创建无向网图*/ int i,j,k,w; edgenode *s; printf(t=无向网图邻接表=n); printf(输入顶点数和边数:); scanf(%d,%d%*c, printf(n 输入顶点:); for(i=0;in;i+) scanf(%d, g-adjlisti.firstedges=null; printf(n 输入边和权值:); for(k=0;ke;k+) scanf(%d,%d,%d, s=(edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-

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

17、 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; k=1; while(jn) if(lowcostjmincost k=j; j+; printf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0; for(j=0;jn;j+) if(gmkjlowcostj) lowcostj=gmkj; closevertexj=k; 6. 输出邻接矩阵存储函数 void output

18、(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; printf(n 网图的邻接表表示如下：n); for (i=0; in; i+) printf(%d,%3d=,i,g-adjlisti.vertex); p=

19、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; for(i=0;ie;i+) for(j=0;je;j+) if(i=j)m-edgesij=0; else m-edgesij=maxv

20、ertexnum; 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); 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 测试数据（对下图进行测试）： 4.2 程序执行过程程序执行过程 系统使用说明： 1. 输入的数据可以是 100 以内的整数； 2. 本系统可以建立带权图，并能够用 prim 算法求该网图的最小生 成树。 3.

21、该系统会有菜单提示，进行选项： 右图是 6 个顶点的 10 条边的 连通图 六个顶点分别是： 1 2 3 4 5 6 顶点序号和边上的权植分别是 0 1 11 0 2 15 0 3 18 1 2 33 1 4 12 2 3 20 2 4 22 2 5 25 3 5 27 4 5 29 1 24 3 5 6 4.程序实际运行截图 （1）有向图邻接矩阵输出最小生成树截图： （2）无向图邻接矩阵输出最小生成树截图： （3）有向图邻接表输出最小生成树截图： （4）无向图邻接表输出最小生成树截图： 参考文献参考文献 （1）李素若， 数据结构（c 语言描述） ，2009，化学工业出版社 （2）严蔚敏、吴伟民， 数据结构（c 语言描述） ，1999，清华大学出 版社 （3）徐孝凯，数据结构课程实验，2002，清华大学出版社