普里姆算法求最小生成树审批稿.docx

YKK standardization office【 YKK5AB- YKK08- YKK2C- YKK18】
普里姆算法求最小生成树
沈阳航空航天大学
课 程 设 计 报 告
课程设计名称：数据结构课程设计
课程设计题目：Prim算法求最小生成树
院（系）：计算机学院
专 业： 计算机科学与技术（物联网方向）
班 级：
学 号：
姓 名：
指导教师：
学术诚信声明
本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。
本人签名: 日期： 2015 年 1 月 15 日
沈阳航空航天大学
课程设计任务书
课程设计名称
数据结构课程设计
专业
计算机科学与技术（物联网方向）
学生姓名
班级
学号
题目名称
Prim算法生成最小生成树
起止日期
2015
年
1
月
5
日起至
2015
年
1
月
16
日止
课设内容和要求：
在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。
参考资料：
算法与数据结构，严蔚敏、吴伟民，清华大学出版社，2006
C程序设计，谭浩强，清华大学出版社，2010
教研室审核意见： 教研室主任签字：
指导教师（签名）
年
月
日
学 生（签名）
2015
年
1
月15
日
目 录
一 课程设计目的和要求
课程设计目的
根据算法设计需要，掌握连通网的数据表示方法；
掌握最小生成树的Prim算法；
学习独立撰写报告文档。
课程设计的要求
在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。
二 实验原理分析
最小生成树的定义
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用（克鲁斯卡尔）算法或（普里姆）算法求出。
最小生成树的概述
在一给定的G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此的权重，若存在 T 为 E 的（即）且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
最小生成树的分析
构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边的最小生成树。
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个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法