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

课程设计报告课程名称：数据结构课程设计设计题目： 克鲁斯卡尔算法求最小生成树 系 别： 计算机系 专 业： 组 别： 学生姓名： 学 号: 起止日期: 2011年6月29日 2011年7月6日 指导教师: 马强 14目 录1. 需求分析2 1.1 设计题目21.2 设计任务及要求21.3课程设计思想21.4 程序运行流程:21.5软硬件运行环境及开发工具22.概要设计2 2.1流程图2 2.2抽象数据类型MFSet的定义3 2.3主程序3 2.4抽象数据类型 图 的定义4 2.5抽象数据类型 树 的定义63. 详细设计8 3.1程序84.调试与操作说明11 4.1测试结果11 4.2调试分析125.课程设计总结与体会12 5.1总结12 5.2体会126. 致谢137. 参考文献138.附录141.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE=开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC2.概要设计 2.1流程图 开始 定义数据类型定义图Mgraphi=0定位定义图中的顶点数和边数Kruskal算法主程序图1流程图 2.2抽象数据类型MFSet的定义：ADT MFSet 数据对象 ：若设S是MFSet型的集合，则它由n(n0)个子集Si（i = 1,2.,n）构成，每个子集的成员代表在这个子集中的城市。数据关系 ： S1 U S2 U S3 U. U Sn = S, Si包含于S（i = 1,2,.n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 2.3主程序：int main()初始化；while (条件) 接受命令; 处理命令;return 0; 2.4抽象数据类型 图 的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R： R=VR VR=|v，wV且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息 基本操作P：CreateGraph（&G，V，VR）； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和的VR定义构造图G。DestoryGraph（&G）； 初始条件：图G存在。 操作结果：销毁图G。LocateVex（G，u）； 初始条件：图G存在，u和G中是顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）； 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。PutVex（&G，v，value）； 初始条件：图G存在，v是G中某个顶点。 操作结果：对V赋值value，FirstAdjVex（G，v）； 初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有顶点，则返回“空”。NextAdjVex（G，v，w）； 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。InsertVex（&G，v）； 初始条件：图G存在，v和途中顶点有相同特征。 操作结果：在图G中添加新顶点v。DeleteVex（&G，v）； 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。InsertArc（&G，v，w）； 初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中添加弧，若G是无向的，则还增添 对称弧。DeleteArc（&G，v，w）； 初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTravrese（G，Visit（）； 初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit一次且仅一次。一旦Visit（）失败，则操作失败。BFSTravrese（G，Visit（）； 初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。 ADT Graph 2.5抽象数据类型 树 的定义如下：ADT Tree数据对象D:D是具有相同特性数据元素的集合。数据关系R：若D为空集，则称为空树； 若D仅含一个元素数 据， 则R为空集，否则R=H，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱； （2）若D-root，则存在D-root的一个划分D1，D2，Dm（m0），对任意jk（1j,km）有DjDk=，且对任意的I（1im），惟一存在数据元素xiDi有H；（3）对应于D-root的划分，H-，有惟一的一个划分H1，H2，Hm（m0），对任意jk(1j，km)有HjHk=，且对任意I（1im），Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为跟root的子树。 基本操作P：InitTree（&T）；操作结果：构造空树T。 DestoryTree（&T）；初始条件：树T存在。 操作结果：销毁树T。 CreateTree（&T，definition）；初始条件：definition给出树T的定义。操作结果：按definition构造树T。 ClearTree（&T）；初始条件：树T存在。操作结果：将树T清为空树。 TreeEmptey（T）；初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则FALSE。 TreeDepth（T）；初始条件：树T存在。操作结果：返回T的深度。 Root（T）；初始条件：树T存在。操作结果：返回T的跟。 Value（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。 Assign（T，cur_e，value）；初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Parent（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左子，否则返回“空”。RightSibling（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。InsertChild（&T，&p，I，c）；初始条件：树T存在，P指向T中某个结点，1ip所指向的结点度数+1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild（&T，&p，i）；初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除T中p所指结点的第i棵子树。TraverseTree（T，Visit（）；初始条件：树T存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit（）一次且至多一次。一旦vista（）失败，则操作失败。ADT Tree3.详细设计 3.1程序：如下#include#include#include#define MAX_NAME 5#define MAX_VERTEX_NUM 20 typedef char VertexMAX_NAME;/*顶点名字串*/typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/typedef struct /*定义图*/Vertex vexsMAX_VERTEX_NUM;AdjMatrix arcs; int vexnum,arcnum; MGraph;typedef struct Vertex adjvex; /*当前点*/ int lowcost; /*代价*/minsideMAX_VERTEX_NUM;int LocateVex(MGraph *G,Vertex u) int i; for(i=0;ivexnum;+i) if(strcmp(G-vexsi,u)=0) return i; return -1;void CreateGraph(MGraph *G) int i,j,k,w; Vertex va,vb; printf(请输入无向网G的顶点数和边数(以空格为分隔)n); scanf(%d %d,&G-vexnum,&G-arcnum); printf(请输入%d个顶点的值(vexnum,MAX_NAME); for(i=0;ivexnum;+i) /* 构造顶点集*/ scanf(%s,G-vexsi); for(i=0;ivexnum;+i) /*初始化邻接矩阵*/ for(j=0;jvexnum;+j) G-arcsij=0x7fffffff; printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,G-arcnum); for(k=0;karcnum;+k) scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G-arcsij=G-arcsji=w; /*对称*/ void kruskal(MGraph G) int setMAX_VERTEX_NUM,i,j; int k=0,a=0,b=0,min=G.arcsab; for(i=0;iG.vexnum;i+) seti=i; printf(最小代价生成树的各条边为:n); while(kG.vexnum-1) for(i=0;iG.vexnum;+i) for(j=i+1;jG.vexnum;+j) if(G.arcsijmin) min=G.arcsij; a=i; b=j; min=G.arcsab=0x7fffffff; if(seta!=setb) printf(%s-%sn,G.vexsa,G.vexsb); k+; for(i=0;iG.vexnum;i+) if(seti=setb) seti=seta; void main() MGraph g; CreateGraph(&g); kruskal(g); system(PAUSE); getch();4. 调试与操作说明 4.1测试结果：如下图图2测试结果1图3测试结果2 4.2调试分析本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而条是比较顺利。在调试过程中主要是参数的传递比较不容易掌握。本程序的关键部分是如何确定一条边的两个端点是否属于同一连通分支，合并两个连通分支。5. 课程设计总结与体会5.1总结：克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件就将其构造，最后生成一个最小生成树。它首先是一系列的顶点集合，并没有边，然后我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，则舍弃，另外取其它的边。如果不连接成环，则接受这个边，并把其纳入集合中。5.2体会： （1）通过求最小生成树，进一步掌握了图的含义，掌握了克鲁斯卡尔算法的基 本思想及流程。知道了克鲁斯卡尔算法与普里姆算法的区别与联系。通过本次课程设计，锻炼了我们的实际操作能力，培养了我们严密的思维和严谨的态度。 （2） 在编程序过程中虽然遇到了很多问题，但也使我学到了很多东西，在编制程序过程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块，并想好所要用到的知识计算法，在编程过程中，特别是要画图时需要找出坐标，并研究各坐标各结点之间连线的规律，通过几句判断语句来实现多条连线问题，在编程过好还要反复调试程序，找出其中的漏洞并加以改正，在此次编程过程中就存在这样的问题，在经过反复修改后，终于可将漏洞扫除，正确的输出结果。6.致谢 在编著过程中，感谢那些帮助我的同学，有了他们，我的课程设计才能顺利进行下去。感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的