VS常用算法演示软件设计图形结构(5)
3.2项目计划
3.2.1编写目的
编写此计划的目的是为了合理安排有效利用时间,以确保项目进度,预见项目风险等活动。使项目严格按照计划开发流程进行,遵循正规的顺序开展。同时,使项目成员即本人通过此计划书明确项目目标和职责。它说明软件的开发方法,是一种计划,以指导开发工作之用
3.2.2项目名称 :常用算法演示软件设计——图形结构
3.2.3 项目背景
2014年上海应用技术学院的毕业季,学院为了考察学生的学业水平,给每一个即将毕业的学生留下的任务,即本次的论文和项目程序,利用在校区间所学的编程语言和算法基础进行一次项目开发
3.2.4 项目概述
常用算法演示软件设计——图形结构是一个关于数据结构的算法演示，主要介绍各种图形算法，并向广大用户提供学习探讨交流的平台。
3.2.5 工作内容
本项目分为:文档和程序两部分
3.2.6交付项
表3.1 交付项表
名称：
开题报告 学生自检表 程序 毕业论文 任务书
交付日期：
2014.4.8 2014.4.30 2014.6 2014.5.26 2013.12.14
描述：
《开题报告》 《学生自检表》 源程序 《毕业论文》 《任务书》
类别： word文档
表格 程序包 word文档 word文档
3.3算法的原理
3.3.1普利姆算法的原理
普里姆算法（Prim算法），一种在图论上的算法，可以与最小生成树的加权搜索图的连通。这意着算法的边子集搜索树，不仅包括所有顶点的连通图，和它的所有边的权和最小。该算法是在1930年由即可数学家切赫亚尔尼克发现；在1957由美国的计算机科学家罗伯特一本正经的独立发现；在1959，艾滋病病例德科斯车再次发现算法。
最小生成树是数据结构中图的一种重要应用，它是加权无向完全图的要求选择N-1 边和是这个数字仍然连接即得到一个生成树，而且要考虑的最小重量的树。为了得到最小生成树，而且要考虑的最小权重的树。
1：初始化：U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。
2：在所有u∈U,v∈V－U的边（u,v）∈E中，找一条权最小的边（u 0,v 0），将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边，要求这条边满足以下条件：首先边的两个顶点要分别在顶点集合U和V－U中，其次边的权要最小。找到这条边以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态的集合，这一点在理解算法时要密切注意。
3：如果U=V，则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时，步骤2共执行了n－1次（设n为图中顶点的数目），TE中也增加了n－1条边，这n－1条就是需要求出的最小生成树的边
输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：new = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
重复下列操作，直到new = V：
在集合E中选取权值最小的边（u, v），其中u为集合new中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
下一篇：浅析欧洲中世纪骑士精神