数据结构课程设计报告最小生成树Kruskal算法


计算机科学技术系


课程设计报告
20142015学年第二学期




课程
数结构
课程设计名称
Kruskal算法求生成树
学生姓名

学号

专业班级
软件工程
指导教师


2014年X月
题目：设计程序完成功：定网起点kruskal算法基思想求解生成树
1问题分析务定义
根课设题目求拟整体程序分三模块三模块体分析：
确定图存储形式通题目求具体分析发现该题操作路径输出采边集数组（元素结构体包括起点终点权值）邻接矩阵较方便编程
Kruskal算法该算法设置集合A该集合直某生成树子集步决定否边（uv）添加集合A中添加条件A∪{（uv）}然生成树子集称样边A安全边安全添加A中会破坏述条件
2 数结构选择概设计
存储结构
定义结构体数组空间足够输入字符串存数组中
struct edges
{int bv
int tv
int w
}
概设计
算法思想 ：
算法会先权重非递减序图中边进行排序然空子图开始扫描序表试图列表中条边加前子图中然种添加应导致回路果产生回路条边跳图顶点包含构造树中算法停止
算法基思路：

K r u s k a l算法次选择n 1条边贪婪准：剩边中选择条会产生环路具耗费边加入已选择边集合中注意选取边产生环路形成棵生成树K r u s k a l算法分e 步中e 网络中边数目耗费递增序考虑e 条边次考虑条边考虑某条边时加入已选边集合中会出现环路抛弃否选入
假设点标号（djpj）中d起源点点j短路径长度（顶点身短路径零路（没弧路）长度等零）pjsj短路径中j点前点求解起源点s点j短路径算法基程：
1） 初始化起源点设置：①ds0ps空②点：di∞pi？③标记起源点s记ks点设未标记
2） k直接连接未标记点j距离设置：
djmin[dj dk+lkj]
式中lkj点kj直接连接距离
3） 选取点未标记结点中选取dj中i：
dimin[dj 未标记点j]
点i选短路径中点设已标记
4）找点i前点已标记点中找直接连接i点j*作前点设置： ij*
5)标记点i果点已标记算法完全推出否记ki转2）继续
程序中求两点间短路径算法步骤：
① 调dijkstra算法
② path中第终点元素回溯起点显示出
3详细设计编码
功模块图
开始
输入顶点数n
输入边数e
输入边集
显示菜单进行选择
求两点间短距离
求两点间短距离
Kruskal算法
结束

图31 功模块图
流程图分析
1 函数
开始
输入顶点数n
输入边数e
输入选项a
a1
调insertsortkruskal函数
a2
输入v0
调dijkstraprintpath1函数
a3
输入v0v1
调dijkstraprintpath2函数
输入a4
结束

图32函数流程图
2 insertsort函数
开始
int ij
for(i2ige[i]wge[0]ge[i]
ji1
ge[0]w ge[j+1]ge[j]
j
Y
ge[j+1]ge[0]
N
Y
结束
N

图33insertsort函数流程图
3．Kruskal函数
开始
int set[MAXE]v1v2ij
for(i1i set[i]0
i1
j1
jv1v2
v1seeks(setge[j]bv)
v2seeks(setge[j]tv)
printf((dd)d＼nge[j]bvge[j]tvge[j]w)
set[v1]v2
i++
j++
Y
Y
结束
N
N


图34 Kruskal函数流程图
4 机调试程
调试程
调试程序时遇类问题：
1 时函数中数组中数法存储
2 进行检验发现没申请空间
3 源程序开头#define定义数值数组时知道空间
4 函数中时出现负值
5 进行检验发现程序中∞32767代cost[u][w]32767cost[u][w]+dist[u]肯定溢出负值造成权值出现负值
6 cost[u][w]32767dist[w]肯定需重新置数if（s[w]0&&cost[u][w]+dist[u]程序执行程
系统说明：
1 输入数整数字符串（123）
2 系统建立带权图够Kruskal算法求改图生成树够选择图意点做根结点够求两点间短距离
3 该系统会菜单提示进行选项：
1kruskal
4exit
5测试结果分析
结果截图

图51 输入形式

图52 kruskal算法输出

图53kruskal算法输出
算法描述
1 Kruskal函数：
Kruskal需序边集数组先边集数组排序次执行中需判断否构成回路需判断函数seeksKruskal中调seeks
2 dijkstra函数：
源余点短路径n1条设变量vnum作计数器控制循环该函数关键dist数组重新置数该置数条件：该顶点访问新起点该点权值加新起点源点权值该点原权值第次设：if（s[w]0&&cost[u][w]+dist[u]6户说明
1 开创天中文c++软件
2 写代码<附录部分>导入软件中运行
3 述说明运行检查程序
7参考文献
[1]王昆仑李红数结构算法北京：中国铁道出版社2006年5月
[2]严蔚敏 吴伟民 数结构（C语言版）清华学出版社2007
[3]张德富 算法设计分析国防工业出版社2009
[4]朱青 计算机算法程序设计清华学出版社2009
[5]徐宝文李志 C程序设计语言机械工业出版社2004
8附 录（关键部分程序清单）
程序代码
#includestdioh
#define MAXE 100
struct edges
{int bv 起点
int tv 终点
int w权值
}
typedef struct edges edgeset

int seeks(int set[]int v) 顶点集顶点v
{
int i
iv
while(set[i]>0)
iset[i]
return i
}

void kruskal(edgeset ge[]int nint e) 边集顶点数n边数e
{

int set[MAXE]v1v2ijxy1 输入顶点集
edgeset xy[MAXE]
for(i1iset[i]0
i1
j1
printf(第d生成树＼n1)判断第生成树

while(j{
v1seeks(setge[j]bv) 起点
v2seeks(setge[j]tv) 终点
if(v1v2)
{
xy[j]ge[j]
printf((dd)d＼nge[j]bvge[j]tvge[j]w)
set[v1]v2
i++ 计数器（判断顶点数否溢出）
}
j++
}
y++

while(ge[j1]wge[j]w){ 输出生成树
printf(第d生成树＼ny)
for(x1x printf((dd)d＼nxy[x]bvxy[x]tvxy[x]w)
}
printf((dd)d＼nge[j]bvge[j]tvge[j]w)
j++
y++
}


}

void insertsort(edgeset ge[]int e) 权值进行排序
{
int ij
for(i2iif(ge[i]w{
ge[0]ge[i]
ji1
while(ge[0]w{
ge[j+1]ge[j]
j
}
ge[j+1]ge[0]
}
}
main()
{
edgeset ge[MAXE]
int anei
printf(请输入顶点数)
scanf(d&n)
printf(请输入边条数)
scanf(d&e)
printf(请输入边信息（起点终点权值）＼n)
for(i1iscanf(ddd&ge[i]bv&ge[i]tv&ge[i]w)
printf(列菜单中进行选择：＼n)
printf(1kruskal算法（（起点终点）权值）：＼n)

printf(2exit（退出）：＼n)
scanf(d&a)
while(a2)
{
switch(a)
{
case 1insertsort(gee)
kruskal(gene)
break

}
printf(列菜单中进行选择：＼n)
printf(1kruskal算法（（起点终点）权值）：＼n)

printf(2exit（退出）：＼n)
scanf(d&a)
}
return 1
}
合肥学院
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档