课程设计---克鲁斯卡尔算法求最小生成树.doc

课程设计报告
课程名称:数据结构课程设计
设计题目: 克鲁斯卡尔算法求最小生成树
系别: 计算机系
专业:
组别:
学生姓名: 学号:
起止日期: 2011年6月29日~2011年7月6日
指导教师: 马强
目录
1. 需求分析……………………………………………………………………………2
设计题目……………………………………………………………………2
设计任务及要求……………………………………………………………2
………………………………………………………………2
程序运行流程:……………………………………………………………2
………………………………………………2
……………………………………………………………………………2
………………………………………………………………………2
………………………………………………3
………………………………………………………………………3
…………………………………………………4
…………………………………………………6
3. 详细设计……………………………………………………………………………8
…………………………………………………………………………8
……………………………………………………………………11
……………………………………………………………………11
……………………………………………………………………12
………………………………………………………………12
…………………………………………………………………………12
…………………………………………………………………………12
6. 致谢…………………………………………………………………………………13
7. 参考文献……………………………………………………………………………13
…………………………………………………………………………………14

设计题目:最小生成树
设计任务及要求:任意创建一个图,利用克鲁斯卡尔算法,求出该图的最小生成树。

课程设计思想:Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网,令T=(U,TE)是G的最小生成树。最短边策略从TE={}开始,每一次贪心选择都是在边集E中选择最短边(u,v),如果边(u,v)加入集合TE中不产生回路,则将边(u,v)加入边集TE中,并将它在集合E中删去。),它使生成树以一种任意的方式生长,先让森林中的树木随意生长,每生长一次就将两棵树合并,最后合并成一棵树。

:
1)提示输入顶点数目;
2)接受输入,按照项目要求产生边权值的随机矩阵;然后求解最小生成树;
3)输出最小生成树并且退出;

软硬件运行环境及开发工具:VC




开始
定义数据类型
定义图Mgraphi==0
定位
定义图中的顶点数和边数
Kruskal算法
主程序
图1流程图
:
ADT MFSet {
数据对象:若设S是MFSet型的集合,则它由n(n>0)个子集Si(i = 1,2...,n)构成,每个子集的成员代表在这个子集中的城市。
数据关系: S1 U S2 U S3 U... U Sn = S, Si包含于S(i = 1,2,...n)
Init (n): 初始化集合,构造n个集合,每个集合都是单成员,根是其本身。rank数组初始化0
Find(x):查找x所在集合的代表元素。即查找根,确定x所在的集合,并路径压缩。
Merge(x, y):检查x与y是否在同一个集合,如果在同一个集合则返回假,否则按秩合并这两个集合并返回真。
}
:
int main()
{
初始化;
while (条件)
{
接受命令;
处理命令;
}
return 0;
}
:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,成为顶点集。
数据关系R:
R={VR}
VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>