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

数据结构（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 数据结构分析数据结构分析.10 3.1 存储结构10 3.2 算法描述12 4 4 调试与分析调试与分析.22 4.1 调试过程22 4.2 程序执行过程22 参考文献参考文献.28 附附 录录.28 第 0 页 共 29 页 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编写算法能够建立带权图，并能够用 prim 算法求该图的最小 生成树。最小生成树能够选择图上的任意一点做根结点。最小生 成树输出采用顶点集合和边的集合的形式。 1.21.2 课程设计要求课程设计要求 1. 可以输入顶点、边数及各路径的权值； 2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表； 3. 可以输出建立的最小生成树； 4. 画出流程图，且函数有必要说明、注释； 5. 课设完成后上交报告及核心代码。 第 1 页 共 29 页 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块 的大体分析： 1. 创建网图并确定网图的存储形式，通过对题目要求的具体分析。 发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩阵（起点、 终点和权值）两种存储结构，方便以后的编程。 2.prim 算法。设置两个新的集合 u 和 t，其中 u 用于存放带权图 g 的最小生成树的结点的集合，t 用于存放带权图 g 的最小生成树边的权 值的集合。其思想是：令集合 u 的初值为 uu0（即假设构造最小生成 树时从结点 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 页 开始开始 显示菜单，选 择输入 1 或 2 选择 1选择 2 调用 createagraph() 函数 结束结束 选择 1 调用 creategraph()函 数 选择 2 调用 createmgraph() 函数 调用 createalgraph() 函数 调用 prim 函数，输出 最小生成树 图 2.2 主函数流程图 2. createmgraph()函数 第 4 页 共 29 页 开始开始 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 (k=0;ke;k+) scanf(“n%d,%d,%d“, 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), 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; 第 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 #define max 1000 typedef int vertextype; typedef int edgetype; typedef struct vertextype vexsmaxvertexnum; edgetype edgesmaxvertexnummaxvertexnum; int n,e; mgraph; （2）邻接表 #define maxvertexnum 100 typedef int vertextype; typedef struct node int adjvex; 第 10 页 共 29 页 int weight; struct node *next; edgenode; typedef 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 页 共 29 页 3.23.2 算法描述算法描述 1. 创建有向网图邻接矩阵存储 void createmgraph(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=max; /*初始化邻接矩阵*/ printf(“输入边对应的两个顶点的序号及权值：“); for (k=0;ke;k+) scanf(“n%d,%d,%d“, 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(“请输入顶点数和边数：“); 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; /*初始化邻接矩阵*/ 第 13 页 共 29 页 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“); printf(“输入顶点数和边数:“); scanf(“%d,%d%*c“, printf(“n 输入顶点:“); for(i=0;in;i+) 第 14 页 共 29 页 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. 创建无向网图邻接表存储 void createalgraph(algraph *g) /*创建无向网图*/ int i,j,k,w; edgenode *s; printf(“t=无向网图邻接表=n“); 第 15 页 共 29 页 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; 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 mincost; int i,j,k; 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 网图的邻接表表示如下：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; 第 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 调试过程调试过程 测试数据（对下图进行测试）： 4.2 程序执行过程程序执行过程 系统使用说明： 1. 输入的数据可以是 100 以内的整数； 2. 本系统可以建立带权图，并能够用 prim 算法求该网图的最小生 成树。 3. 该系统会有菜单提示，进行选项： 右图是 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 第 22 页 共 29 页 4.程序实际运行截图 （1）有向图邻接矩阵输出最小生成树截图： 第 23 页 共 29 页 （2）无向图邻接矩阵输出最小生成树截图： 第 24 页 共 29 页 第 25 页 共 29 页 （3）有向图邻接表输出最小生成树截图： 第 26 页 共 29 页 （4）无向图邻接表输出最小生成树截图： 第 27 页 共 29 页 参考文献参考文献 （1）李素若， 数据结构（c 语言描述） ，2009，化学工业出版社 （2）严蔚敏、吴伟民， 数据结构（c 语言描述） ，1999，清华大学出 版社 （3）徐孝凯，数据结构课程实验，2002，清华大学出版社 （4）孟佳娜、胡潇琨，算法与数据结构实验与习题，20