普里姆算法求最小生成树.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 PrimPrim 算法求最小生成树算法求最小生成树 院 系 计算机学院 专 业 计算机科学与技术 物联网方向 班 级 学 号 姓 名 指导教师 0 学术诚信声明 本人声明本人声明 所呈交的报告 含电子版及数据文件 是我个人在导师指 导下独立进行设计工作及取得的研究结果 尽我所知 除了文中特别 加以标注或致谢中所罗列的内容以外 报告中不包含其他人己经发表 或撰写过的研究结果 也不包含其它教育机构使用过的材料 与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明 并表示了谢意 报告资料及实验数据若有不实之处 本人愿意接受本 教学环节 不及格 和 重修或重做 的评分结论并承担相关一切后 果 本人签名 日期 2015 年 1 月 15 日 1 沈阳航空航天大学沈阳航空航天大学 课课程程设设计计任任务务书书 课程设计名称 数数据据结结构构课课程程设设计计专业 计算机科学与技术计算机科学与技术 物联网方向 物联网方向 学生姓名班级学号 题目名称Prim 算法生成最小生成树算法生成最小生成树 起止日期2015年1月5日起至2015年1月16日止 课设内容和要求 在 n 个城市之间建立网络 只需保证连通即可 求最经济的架设方法 利用 Prim 算法输出 n 个城市之间网络图 输出 n 个节点的最小生成树 其中 n 个城 市表示 n 个节点 两个城市间如果有路则用边连接 生成一个 n 个节点的边权树 要求键盘输入 参考资料 算法与数据结构 严蔚敏 吴伟民 清华大学出版社 2006 C 语言程序设计 谭浩强 清华大学出版社 2010 教教研研室室审审核核意意见见 教教研研室室主主任任签签字字 指导教师 签名 指导教师 签名 年月日 2 学学 生 签名 生 签名 2015年1 月 15 日 3 目目 录录 学术诚信声明学术诚信声明 1 一一 课程设计目的和要求课程设计目的和要求 4 1 1 课程设计目的 4 1 2 课程设计的要求 4 二二 实验原理分析实验原理分析 5 2 1 最小生成树的定义 5 2 2 PRIM算法的基本思想 5 三三 概要分析和设计概要分析和设计 7 3 1 概要分析 7 3 2 概要设计 8 四四 测试结果测试结果 13 4 1实验一 13 4 2实验二 13 4 3 实验三 14 参考文献参考文献 15 附附 录 关键部分程序清单 录 关键部分程序清单 16 4 一 课程设计目的和要求 1 1 课程设计目的课程设计目的 一 根据算法设计需要 掌握连通网的数据表示方法 二 掌握最小生成树的 Prim 算法 三 学习独立撰写报告文档 1 2 课程设计的要求课程设计的要求 在 n 个城市之间建立网络 只需保证连通即可 求最经济的架设方法 利用 Prim 算法输出 n 个城市之间网络图 输出 n 个节点的最小生成树 其中 n 个城 市表示 n 个节点 两个城市间如果有路则用边连接 生成一个 n 个节点的边权树 要求键盘输入 5 二 实验原理分析 2 1 最小生成树的定义最小生成树的定义 一个有 n 个结点的连通图的生成树是原图的极小连通子图 且包含原图中 的所有 n 个结点 并且有保持图连通的最少的边 最小生成树可以用 kruskal 克鲁斯卡尔 算法或 Prim 普里姆 算法求出 1 最小生成树的概述 在一给定的无向图 G V E 中 u v 代表连接顶点 u 与顶点 v 的边 即 而 w u v 代表此边的权重 若存在 T 为 E 的子集 即 且为无循 环图 使得 w T 最小 则此 T 为 G 的最小生成树 最小生成树其实是最小权重生成树的简称 2 最小生成树的分析 构造最小生成树可以用多种算法 其中多数算法利用了最小生成树的 下面一种简称为MST 的性质 假设N V E 是一个连通网 U 是顶 点集 V 的一个非空子集 若 u v 是一条具有最小权值 代价 的边 其 中 u U v V U 则必存在一棵包含边 u v 的最小生成树 2 2 Prim 算法的基本思想算法的基本思想 假设 G V E 是一个具有 n 个顶点的连通网 T U TE 是 G 的最小生成 树 其中 U 是 T 的顶点集 TE 是 T 的边集 U 和 TE 的初值均为空集 算法开始 时 首先从 V 中任取一个顶点 假定取 V0 将它并入 U 中 此时 U V0 然后 只要 U 是 V 的真子集 就从那些其一个端点已在 T 中 另一个端点仍在 T 外的所 有边中 找一条最短 即权值最小 边 假定为 i j 其中 Vi U Vj V U 并把该边 i j 和顶点 j 分别并入 T 的边集 TE 和顶点集 U 如此进行下去 每 次往生成树里并入一个顶点和一条边 直到 n 1 次后就把所有 n 个顶点都并入到 6 生成树 T 的顶点集中 此时 U V TE 中含有 n 1 条边 T 就是最后得到的最小生 成树 可以看出 在普利姆算法中 是采用逐步增加 U 中的顶点 常称为 加点 法 为了实现这个算法在本设计中需要设置一个辅助数组 closedge 以记录 从 U 到 V U 具有最小代价的边 当辅助数组中存在两个或两个以上的最小代价的 边时 此时最小生成树的形态就不唯一 此时可以在程序中采用递归的算法思想 求出每个最小生成树 1 在 prim 算法中要解决两个问题 1 在无向网中 当从一个顶点到其他顶点时 若其边上的权值相等 则可能从 某一起点出发时 会得到不同的生成树 但最小生成树的权值必定相等 此 时我们应该如何把所有的最小生成树求解出来 2 每次如何从生成树 T 中到 T 外的所有边中 找出一条权值最小的边 例如 在第 k 次 1 k n 1 前 生成树 T 中已有 k 个顶点和 k 1 条边 此时 T 中 到 T 外的所有边数为 k n k 当然它也包括两顶点间没有直接边相连 其权 值被看作常量的边在内 从如此多的边中找出最短的边 其时间复杂度 0 k n k 是很费时间的 是否有好的方法能够降低查找最短边的时间复 杂度 2 上述问题的解决方法 针对 1 中出现的问题 可以通过算法来实现 详情请看 Prim 算法的概述 针对 2 中出现的问题 通过对 Prim 算法的分析 可以使查找最短边的时间 复杂度降低到 O n k 具体方法是假定在进行第 k 次前已经保留着从 T 中到 T 外 的每一顶点 共 n k 个顶点 的各一条最短边 进行第 k 次时 首先从这 n k 条 最短边中 找出一条最最短的边 它就是从 T 中到 T 外的所有边中的最短边 假 设为 i j 此步需进行 n k 次比较 然后把边 i j 和顶点 j 分别并入 T 中的边 集 TE 和顶点集 U 中 此时 T 外只有 n k 1 个顶点 对于其中的每个顶点 t 若 j t 边上的权值小于已保留的从原 T 中到顶点 t 的最短边的权值 则用 j t 修改之 使从 T 中到 T 外顶点 t 的最短边为 j t 否则原有最短边保持不变 这 样 就把第 k 次后从 T 中到 T 外每一顶点 t 的各一条最短边都保留下来了 为进 7 行第 k 1 次运算做好了准备 此步需进行 n k 1 次比较 所以 利用此方法求第 k 次的最短边共需比较 2 n k 1 次 即时间复杂度为 O n k 8 三 概要分析和设计 3 1 概要分析概要分析 通过对上述算法的分析 将从以下三方面来进行分析 1 输入数据的类型 在本次设计中 是对无向图进行操作 网中的顶点数 边数 顶点的编号及 每条边的权值都是通过键盘输入的 他们的数据类型均为整型 其中 权值的范 围为 0 32768 即 2 输出数据的类型 当用户将无向图创建成功以后 就可以通过键盘任意输入一个起点值将其对 应的最小生成树的生成路径及其权值显示出来 3 测试数据 本次设计中是通过用 Prim 算法求最小生成树 分别用以下三组数据进行测 试 一 假设在创建无向图时 只输入一个顶点 如图 1 所示 验证运行结果 图 1 单一节点的无向图 二 假设创建的无向图如图 2 所示 验证运行结果 A 9 图 2 网中存在权值相等的边 三 假设创建的无向图如图 3 所示 验证结果 图 3 网中的权值各不相等 3 2 概要设计概要设计 在本次设计中 网的定义为 G V E V 表示非空顶点集 E 表示边集 其存储结 构这里采用邻接矩阵的方式来存储 1 数据类型的定义 在本设计中所涉及 10 到的数据类型定义如下 1 符号常量的定义 算法中涉及到两个符号常量 定义如下 define MAX 20 功能 用于表示网中最多顶点个数 define INFINIT 32768 功能 用于表示权的最大值 即 2 结构体的定义 整个算法中涉及的结构体定义如下 定义结构体 ArcNode 功能 用于存放边的权值 typedef struct int adj 权值 ArcNode 定义结构体 AdjMatrix 功能 用于表示网的结构及存储方式 typedef struct int vexs MAX vexs 表示顶点向量 int vexnum arcnum 分别表示图的顶点数和弧数 ArcNode arcs MAX MAX 邻接矩阵 AdjMatrix 定义结构体 Node 功能 用于表示求最小生成树时用到的辅助数组 typedef struct int adjvex 存放顶点编号 int lowcost 存放顶点权值 Node 外部变量的定义 算法中涉及到两个外部变量 定义如下 11 Node close MAX 功能 存放每个顶点所连接的边所对应的权值 int flag 0 功能 标志变量 当创建网时 输入的顶点个数 1 时 直接输出 不存在最小生成树 程序不在往后执行 否则继续往下执行 3 函数模块 在本设计中一共包括六个模块 一 子函数 int Locate AdjMatrix G int V 功能 是求出某个顶点在顶点向量表中的位置 在其函数体中通过 for 循环 将某一顶点与顶点向量表中的所有顶点进行比较 当出现两者相等时 将该顶点 在 vexs MAX 数组中的下标通过 return 语句返回 否则返回 1 二 子函数 AdjMatrix creat AdjMatrix G 功能 是完成无向网的创建 在其函数体中 首先通过键盘输入网中顶点数 若顶点个数vexnum 其中 调 用函数 Minium 求出辅助数组 close 中权值最小的边 并将其在辅助数组中的 相应位置返回到主调函数中并赋给 k0 此时 close k0 中存有当前最小边 u0 v0 的信息 将边所对应的终点放入 p 的顶点向量表中 累加边的权值 然后 输出 最后 在顶点 v0 并入 U 之后 利用 for 循环更新 closedge i 当所有的顶点 v0 都纳入 U 集合之后 输出最小生成树中的顶点序 列及最小生成树的权值之和 五 子函数 void display AdjMatrix G 功能 是创建的无向网所对应的邻接矩阵 六 主函数 void main 功能 是完成对上述各子函数的调用 完成本次设计的要求 在其函数体中 通过 while 循环可以实现重复创建网以及可以从网中的不同顶点出发求出对应的 最小生成树 4 流程图 13 开始 输入 ch 用于判断是否创建 无向网 Ch Y 结束 输入起点 st 1 调用 create 函数 2 调用 display 函数 Flog 0 st 0 3 调用 prim 函数 4 调用 minium 函数 图 4 流程图 上述流程图反映了整个算法中各个子函数之间的嵌套调用 从主函数开始顺 序往下执行 首先调用 creat 函数创建无向网并采用邻接矩阵的方式来存储 然后将该网对应的邻接矩阵通过调用 display 函数输出 最后调用 prim 函 数求出该网所对应的最小生成树 并且在 prim 函数中通过嵌套调用 Minium 函 数求出辅助数组 close 中权值最小的边 从而完成了本设计的要求 14 四 测试结果 该部分是对前面任务定义中的测试数据进行验证和分析 4 1实验一实验一 只含一个顶点的无向图 图 5 只含一个顶点的无向图 4 2实验二实验二 假定创建的无向网的顶点个数 1 并且网中有些边的权值相等 15 图 7 运行结果 分析 在上述创建的无向网中 有些顶点之间没有边相连接 所以在邻接矩 阵中用 表示 由于是以顶点 1 作为起点生成最小生成树 所以上述运行结果对 应的生成树如图 7 所示 4 3 实验三实验三 假定创建的无向网的顶点个数 1 并且网中有些边的权值不相等 运行结果 如下 16 参考文献 1 吴玉蓉 数据结构 C 语言版 中国水利水电出版社 2008 年 2 徐孝凯 数据结构实用教程 清华大学出版社 2005 年 7 月 3 谭浩强 C 语言程序设计教程 高等教育出版社 2004 年 5 月 17 附 录 关键部分程序清单 include stdio h include string h include malloc h include iostream h include iomanip h define MAX 20 最多顶点个数 define INFINIT 32768 表示极大值 即 typedef struct int adj adj 是权值类型 ArcNode typedef struct int vexs MAX vexnum arcnum vexs 表示顶点向量 vexnum arcnum 分别表示图的顶点数和弧数 ArcNode arcs MAX MAX 邻接矩阵 AdjMatrix typedef struct int adjvex 存放顶点编号 int lowcost 存放顶点权值 Node Node close MAX 求最小生成树时的辅助数组 int flag 0 功能 标志变量 当创建网时 输入的顶点个数 1 时 直接输出 不存在最小生成树 程序 不在往后执行 否则继续往下执行 int Locate AdjMatrix G int V 求顶点位置函数 int j 1 k for k 0 kvexnum k if G vexs k V j k 18 break return j AdjMatrix creat AdjMatrix G 创建无向网 int i j k v1 v2 weight m 1 printf 请输入网中的顶点数 scanf d if G vexnumarcnum for i 0 ivexnum i 初始化邻接矩阵 for j 0 jvexnum j if i j G arcs i j adj 0 else G arcs i j adj INFINIT printf 请输入网中的顶点编号 输入网中的顶点编号 for i 0 ivexnum i scanf d printf 输入每条弧所对应的两个顶点及权值 n for k 0 karcnum k printf 请输入第 d 条边 m m scanf d d d 输入一条弧的两个顶点及权值 i Locate G v1 j Locate G v2 G arcs i j adj weight G arcs j i adj weight return G 19 int Minium AdjMatrix G Node close close 中权值最小的边 int i min k min INFINIT 置最小权值为 INFINIT for i 0 ivexnum i if close i lowcostvexs n u close k lowcost 0 初始化 U u for i 0 ivexnum i if i k 对 V U 中的顶点 i 初始化 close i close i adjvex u close i lowcost G arcs k i adj for j 1 jvexnum 1 j n 1 条边 n G vexnum k0 Minium G close close k0 中存有当前最小边 u0 v0 的信息 u0 close k0 lowcost u0 U v0 G vexs k0 v0 V U p vexs n v0 将终点放入数组中 s close k0 lowcost 求最小生成树的权值之和 printf d t d n u v0 close k0 lowcost 输出最小生成树的路径 close k0 lowcost 0 将顶点 v0 纳入 U 集合 for i 0 ivexnum i 在顶点 v0 并入 U 之后 更新 closedge i 20 if G arcs k0 i adjarcs k0 i adj close i adjvex v0 printf n 最小生成树中的顶点序列为 for i 0 ivexnum i printf d p vexs i printf n printf n 最小生成树的权值之和为 d n s void display AdjMatrix G 输出邻接矩阵算法 int i j for i 0 ivexnum i printf t d G vexs i printf n printf for i 0 ivexnum i printf printf n for i 0 ivexnum i printf d G vexs i for j 0 jvexnum j if G arcs i j adj INFINIT printf t else printf t d G arcs i j adj printf n for i 0 ivexnum i printf printf n void main 主函数 char ch int st 21 AdjMatrix G p p AdjMatrix malloc sizeof AdjMatrix printf n printf 普里姆最小生成树算法 n printf n n printf 设 计 者 李浩渊 n printf 班 级 34010105 班 n printf 指导老师 范纯龙老师 n printf 设计时间 201