Kruskal算法求最小生成树doc教学教材.docx
- 文档编号:14009391
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:14
- 大小:92.62KB
Kruskal算法求最小生成树doc教学教材.docx
《Kruskal算法求最小生成树doc教学教材.docx》由会员分享,可在线阅读,更多相关《Kruskal算法求最小生成树doc教学教材.docx(14页珍藏版)》请在冰点文库上搜索。
Kruskal算法求最小生成树doc教学教材
Kruskal算法求最小生成树.doc
荆楚理工学院
课程设计成果
学院:
_______计算机工程学院__________班级:
14计算机科学与技术一班
学生姓名:
陈志杰学号:
2014407020137
设计地点(单位)_____B5101_____________________
设计题目:
克鲁斯卡尔算法求最小生成树__________________________________
完成日期:
2015年1月6日
指导教师评语:
_______________________________________
____________________________________________________________________________________________________________________________________________________________________________________________________________________
成绩(五级记分制):
________________
教师签名:
_________________________
《数据结构》课程设计评分表
班级
计科一班
姓名
陈志杰
指导教师
李素若
题目:
克鲁斯卡尔算法求最小生成树
评分标准
评分标准
分数权重
评分的依据
得分
A
C
选题
10
选题符合大纲要求,题目较新颖,工作量大
选题基本符合大纲要求,工作量适中
工作态度
10
态度端正,能主动认真完成各个环节的工作,不迟到早退,出勤好。
能够完成各环节基本工作,出勤较好。
系统设计
20
能正确描述总体系统框架图,主要函数有正确的流程图。
能基本正确描述总体系统框架图,主要函数基本能给出流程图。
独立解决问题的能力
10
具有独立分析、解决问题能力,有一定的创造性,能够独立完成数据库及相关软件的设计与调试工作,程序结构合理,逻辑严谨,功能完善。
有一定的分析、解决问题能力。
能够在老师指导下完成软件的设计与调试工作,程序功能较完善。
答辨问题回答
20
能准确回答老师提出的问题
能基本准确回答老师提出的问题
程序运行情况
10
程序运行正确、界面清晰,测试数据设计合理。
程序运行正确、界面较清晰,能给出合适的测试数据。
课程设计论文
20
格式规范,层次清晰,设计思想明确,解决问题方法合理,体会深刻。
格式较规范,设计思想基本明确,解决问题方法较合理。
总分
指导教师(签字):
注:
介于A和C之间为B级,低于C为D级和E级。
按各项指标打分后,总分在90~100为优,80~89为良,70~79为中,60~69为及格,60分以下为不及格。
1需求分析
1.1系统目标
Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。
其基本思想是:
首先选取全部的n个顶点,将其看成n个连通分量;然后按照网中边的权值由小到大的顺序,不断的选取当前未被选取的边集中权值最小的边。
依照生成树的概念,n个结点的生成树有n-1条边,故反复上述过程,直到选取了n-1条边为止,就构成了一棵最小生成树。
1.2主体功能
在城市规划设计中,假设有n个城市之间建立通信网,则连通n个城市只需n-1条线路。
这里自然考虑怎样建立这n-1条路是总费用最省。
把这n个城市抽象成一个连通网,网的顶点表示各个城市,顶点与顶点之间的边表示通信线路,各个城市之间的通讯线路看作边,相应的建设花费作为边的权,这样就构成了一个网络。
由于在n个城市之间,可行线路有(n*(n-1))/2条,那么,如果选择其中的n-1条线路(边)在n个城市间建成全都能相互通讯的网,并且总的建设花费为最小?
这就是求该网络的最小生成树问题。
本程序的目的是要建立一棵生成树使总费用最少。
1.3开发环境
装有Windows7操作系统的PC机vc++6.0,奔腾41.0GHz以上的处理器,编写的程序需要在32MB的内存中运行。
推荐在以下基本配置电脑中运行:
CPUIntelMMX233MHz内存:
64MB
硬盘空间:
1.5GB
显卡:
4MB显存以上的PCI、AGP显卡
声卡:
最新的PCI声卡
CD-ROM:
8x以上CD-ROM
2概要设计
2.1功能模块划分
运行程序后,程序在内存中申请图g的邻接矩阵表示空间,存放作为用整型数组表示的顶点、边、权值的数据。
程序运行过程中调用存放在存放在ESP寄存器中的数据,寄存器中存放着数据、地址和函数传递的中间结果。
Kruskal算法在调用寄存器中的整型数据,对边上的权值进行冒泡排序,将权值小的边放在数组的上面,然后在进行一次循环打印,循环过程中调用vset辅助数组的数据进行比较,两个数据不相等就将该边打印出来,不断进行这个过程直至打印出n-1条边(即顶点数减一的次数)。
具体的功能流程图如下图2.1功能流程图所示。
图2.1功能流程图
2.2系统流程图
输入网图的信息后,将网图的边、顶点、边上的权值记录在一个邻接矩阵中,在后面的kruskal算法中直接扫描邻接矩阵,将边的信息存放在算法定义的边集数组中。
图2.2系统流程图
3详细设计
3.1数据结构
在Kruskal算法中的数据存放和调用采用整型变量,设置邻接矩阵的最大顶点数,设置图的顶点信息为字符,设置边上权值为整型,定义邻接矩阵图的顶点信息表还有图的顶点数和边数。
Kruskal算法中有一个辅助数组,这里的存放的顶点信息的一维数组vexs的类型是用VertexType类型来表示的,这里把它定义成字符,在实际应用中可以根据需要把它重新定义为其他系统预定义类型或结构类型。
此外,邻接矩阵edges的类型用EdgeType类型表示,这里把它定义为整型。
在实际应用中,若权值的类型是其他数据类型,则只需简单修改即可。
3.2模块设计
1.CreateMGraph创建一个邻接矩阵存储的图。
在提示下输入无向图的顶点数和边数,然后再输入各个顶点的信息,也就是顶点的编号,再输入顶点数组编号的下标表示的边和边上的权值,这中间非网图的边的权值为1。
2.Kruskal算法在扫描到邻接矩阵存放的信息后,用冒泡排序将边上的权值从小到大排列。
定义一个辅助数组,该数组是用来判断生成树中是否会出现回路,也就是生成正确的最小生成树。
判断边的连通分量编号不相等,将这条边打印出来,并将连通分量编号修改。
循环顶点数减一次,将最小生成树打印出来。
4测试
4.1测试数据
主要的测试过程有两个:
1.对邻接矩阵的输入和存放。
克鲁斯卡尔算法运行,得出最小生成树。
2.克鲁斯卡尔算法对存放的邻接矩阵的调用。
输入图的信息后算法得到正确结果。
调试阶段最重要的还是耐性和细心。
要有足够的耐性去对待令人烦躁的错误,一步步细心的调试,就会查出错误的所在。
我们进行调试、测试是为了让我们的代码、程序更加健壮,质量更高。
所以,我们不要畏惧报错,这是个学习进步的过程。
3.调试过程中的输入数据。
第一组测试数据见表4-1。
表4-1调试数据
权值
50
60
40
65
52
45
50
30
42
70
顶点i
1
2
4
3
3
6
4
5
6
5
顶点j
0
0
1
1
2
2
3
3
3
4
第二组测试数据:
表4-2调试数据
权值
1
1
1
1
1
1
顶点i
1
2
3
4
3
4
顶点j
0
0
0
0
1
2
第三组数据:
表4-3调试数据
权值
1
6
4
2
5
3
顶点i
1
2
3
2
3
3
顶点j
0
0
0
1
1
2
4.2测试分析
1.第一组数据测试结果
运行程序后输入图的信息。
按照提示的格式输入,输入成功如下图4.1所示。
图4.1输入图的信息后的界面
输完信息后,程序运行得到最小生成树的结果。
图4.2求得的最小生成树
2.第二组数据测试结果
运行程序后输入图的信息。
按照提示的格式输入,输入成功如下图4.3所示。
图4.3输入图的信息后的界面
输完信息后,程序运行得到最小生成树的结果。
图4.4求得的最小生成树
3.第三组数据测试结果
运行程序后输入图的信息。
按照提示的格式输入,输入成功如下图4.5所示。
图4.5输入图的信息后的界面
输完信息后,程序运行得到最小生成树的结果。
图4.6求得的最小生成树
5总结与体会
5.1总结:
克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边,如果满足条件就将其构造,最后生成一个最小生成树。
它首先是一系列的顶点集合,并没有边,然后我们从邻接矩阵中寻找最小的边,看看它是否和现有的边连接成一个环,如果连接成环,则舍弃,另外取其它的边。
如果不连接成环,则接受这个边,并把其纳入集合中。
5.2体会:
在编程序过程中虽然遇到了很多问题,但也使我学到了很多东西,在编制程序过程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块,并想好所要用到的知识及算法,在编程过程中,特别是要画图时需要找出坐标,并研究各坐标各结点之间连线的规律,通过几句判断语句来实现多条连线问题,在编程过好还要反复调试程序,找出其中的漏洞并加以改正,在此次编程过程中就存在这样的问题,在经过反复修改后,终于可将漏洞扫除,正确的输出结果。
参考文献
[1]李素若,陈万华,游明坤.数据结构.北京:
中国水利水电出版社,2014.
[2]严蔚敏,吴伟民.数据结构(C语言版).北京:
清华大学出版社,2014.
[3]李素若,任正云,赖玲.C语言程序设计. 北京:
:
中国水利水电出版社, 2014.
[4]邓文华.数据结构(C语言版).北京:
清华大学出版社,2011.
附录全部代码
#include
#include
#defineMaxVerNum100//设置邻接矩阵的最大顶点数
typedefcharVertexType;//设置图的顶点信息为整型
typedefintEdgeType;//设置边上权值为整型
typedefstruct{
VertexTypevexs[MaxVerNum];//图的顶点信息表
EdgeTypeedge[MaxVerNum][MaxVerNum];//图的邻接矩阵
intn,e;//图的顶点数和边数
}MGraph;//图的邻接矩阵表示结构定义
voidCreateMGraph(MGraph*g)//建立图g的邻接矩阵表示
{
inti,j,k,w;
printf("输入顶点数和边数(格式为:
顶点数,边数)\n");
scanf("%d,%d",&g->n,&g->e);
printf("输入顶点的信息:
\n");
for(i=0;i
{
getchar();
scanf("%c",&(g->vexs[i]));
}
for(i=0;i
for(j=0;j
g->edge[i][j]=0;//图的遍历算法初始化该值为0
for(k=0;k
{
printf("输入边的两个顶点号的下标,权值w(非网图权值为1)(格式为*,*,*):
\n");
scanf("%d,%d,%d",&i,&j,&w);
g->edge[i][j]=w;
g->edge[j][i]=w;
}
}
voidkruskal(MGraph*g)
{
inti,j,k,s1,s2,num,vest[MaxVerNum];//vset辅助数组
intv1,v2;
structedgeType{//定义边信息结构
intu,v;//每条边两个顶点的数组下标号
intw;//权值
}t,*edge;
edge=(structedgeType*)malloc(g->e*sizeof(structedgeType));
k=0;
for(i=0;i
for(j=0;j
if(g->edge[i][j]&&i { edge[k].u=i;edge[k].v=j; edge[k].w=g->edge[i][j]; k++; } for(j=1;j for(i=0;i if(edge[i].w>edge[i+1].w) { t=edge[i]; edge[i]=edge[i+1]; edge[i+1]=t; } for(i=0;i num=1;//构造生成树的第几条边,从1开始 j=0;//从边集数组下标0开始处理 while(num { v1=edge[j].u;v2=edge[j].v;//取边的两个顶点号 s1=vest[v1];s2=vest[v2];//分别求两个顶点的连通分量的编号 if(s1! =s2) { printf("(%c,%c)--weight=%d\n",g->vexs[v1],g->vexs[v2],edge[j].w); num++; for(i=0;i if(vest[i]==s2)vest[i]=s1;//将vset值为s2的顶点的vset值改为s1 } j++; } } voidmain() { MGraph*g=(MGraph*)malloc(sizeof(MGraph));//申请图g的邻接矩阵表示空间 CreateMGraph(g); kruskal(g); system("PAUSE"); getchar(); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Kruskal 算法 最小 生成 doc 教学 教材