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

《普里姆算法生成最小生成树课程设计》由会员分享，可在线阅读，更多相关《普里姆算法生成最小生成树课程设计（31页珍藏版）》请在毕设资料网上搜索。

1、 数据结构（C 语言描述） 课程设计 学 院 计算机工程学院 班 级 12 级软件技术 1 班 学 号 学生姓名 指导教师 2014年 1月 3 日 目目 录录 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 算法描述 . 10 4 4 调试与分析调试与分析 22 4.1 调试过程 . 22 4.2 程序执行过程

2、 . 22 参考文献参考文献 28 附附 录录 28 第 1 页 共 29 页 1 1 课程设计介绍课程设计介绍 1.1 1.1 课程设计内容课程设计内容 编写算法能够建立带权图， 并能够用 Prim 算法求该图的最小 生成树。 最小生成树能够选择图上的任意一点做根结点。 最小生成 树输出采用顶点集合和边的集合的形式。 1.2 1.2 课程设计要求课程设计要求 1. 可以输入顶点、边数及各路径的权值； 2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表； 3. 可以输出建立的最小生成树； 4. 画出流程图，且函数有必要说明、注释； 5. 课设完成后上交报告及核心代码。 第 2 页 共 29

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

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

5、出最小生成树 结束 开始 第 4 页 共 29 页 图 2.2 主函数流程图 2. CreateMGraph()函数 开始开始 显示菜单，选择 输入 1 或 2 选择 1 选择 2 调 用 createAgraph() 函数 结束结束 选择 1 调用 CreateGraph()函 数 选择 2 调用 CreateMGraph() 函数 调用 createALgraph() 函数 调用 Prim 函数， 输出最 小生成树 第 5 页 共 29 页 图 2.3 CreateMGraph()函数流程图 开始开始 int i,j,k for(i=0;in;i+) scanf(“n%c”, for(i=

6、0;in;i+) for(j=0;in;i+) i=j G-edgesij=0; Y N 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); 结束结束 第 6 页 共 29 页 3Prim()函数 开始开始 int i,j,k,lowcost100,mincost; for(i=1;iadjlisti.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; 第 9 页 共