克鲁斯卡尔算法求最小生成树

1、1. 需求分析21.1设计题目21.2设计任务及要求21.3课程设计思想2 1.4 程序运行流程21.5软硬件运行环境及开发工具22. 概要设计22.1流程图22.2抽象数据类型MFSet的定义3-2.3主程序42.4抽象数据类型图的定义4-2.5抽象数据类型树的定义5-3. 详细设计73.1程序74. 调试与操作说明104.1测试结果10 4.2调试分析115. 课程设计总结与体会115.1总结11 5.2体会116. 致谢127. 参考文献12 1. 需求分析1.1设计题目：最小生成树1.2设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的 最小生成树。1.3课程设计思想：Kr

2、uskal算法采用了最短边策略(设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流程图图1

3、流程图2.2抽象数据类型MFSet的定义：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 数组初始化0Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则 按秩合并这两个集合并返回真

4、。2.3主程序：int main()初始化；while (条件)接受命令；处理命令;return 0;2.4抽象数据类型图的定义如下：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>的意义或信息 基本操作P:CreateGraph (&G , V, VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和的VR定义构造图GoDestoryGrap

5、h (&G );初始条件：图G存在。操作结果：销毁图GoLocateVex (G, u);初始条件：图G存在，u和G中是顶点有相同特征。操作结果：若G中存在顶点u，贝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

6、，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中添加弧v，w，若G是无向的，则还增添对称弧v，w。DeleteArc （ &G，v，

7、w）；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧v，w，若G是无向的，则还删除对称弧v ,w。DFSTravrese （G，Visit （）；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 Visit （）失败，则操作失败。BFSTravrese （G，Visit （）;初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数 Visit 一次且仅一次。一旦 Visit （）失败，则操作失败。ADT Graph2.5抽象数据类

8、型树的定义如下：ADT Tree数据对象D:D是具有相同特性数据元素的集合。数据关系R:若D为空集，则称为空树；若D仅含一个元素数据，则R为空集， 否则R=H ， H是如下二兀关系：(1 )在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若 D-root工，则存在 D-root的一个划分 Di,D2,，Dm(m>0 )， 对任意j枠(1 <j,k <m )有Dj ADk=，且对任意的I (1 <i <m ),惟一存在数据 元素 Xi Di 有vroot , xi> H ;(3) 对应于 D-root的划分，H-<root , xi

9、>，<roor , xm>有惟一 的一个划分 H1, H2，Hm (m >0),对任意 j球(1 <j, k<m)有 HjAHk= 且对任意I (1 <i<m ), Hi是Di上的二元关系，(Di, Hi)是一棵符合本定义的 树，称为跟root的子树。基本操作P:InitTree (&T )；操作结果：构造空树T。DestoryTree (&T )；初始条件：树T存在。操作结果：销毁树ToCreateTree (&T , definition )；初始条件：definition 给出树T的定义。操作结果：按definiti

10、on 构造树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。Pare

11、nt （ 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中某个结点，1 <i&

12、lt;p所指向的结点度数+1， 非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild （&T，&p，i）；初始条件：树T存在，p指向T中某个结点，1 <i<p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。TraverseTree （T，Visit （）;初始条件：树T存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit （） 一次且至多一次。 一旦vista （）失败，则操作失败。ADT Tree3. 详细设计3.1程序：如下#i nclude<stdio.h>#i nc

13、lude<stdlib.h>#i nclude<stri ng.h>#defi ne MAX_NAME 5#defi ne MAX_VERTEX_NUM 30typedef char VertexMAX_NAME;/* 顶点名字数组 */邻接矩typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/* 阵*/typedef struct /* 定义图 */Vertex vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;MGraph;int LocateVex(MGr

14、aph *G,Vertex u)int i;for(i=0;i<G->vex nu m;+i)if(strcmp(G->vexsi,u)=O)return i;return -1;void CreateGraph(MGraph *G)int i,j,k,w;Vertex va,vb;printf("请输入无向网G的顶点数和边数(以空格作为间隔):n");scanf("%d %d",&G->vex num,&G->arcnum);printf("请输入%d个顶点的名字(小于%d个字符):n"

15、,G->vex nu m,MAX_NAME);for(i=0;i<G->vexnum;+i) /*构造顶点集 */sca nf("%s",G->vexsi);for(i=0;i<G->vexnum;+i) /*初始化邻接矩阵 */for(j=0;j<G->vex nu m;+j)G->arcsij=0x7fffffff;printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):n",G->arc nu m);for(k=0;k<G->arc nu m;+k)sea nf(&

16、quot;%s%s%d%*c",va,vb，&w);i=LocateVex(G,va);j=LocateVex(G,vb);G->arcsij=G->arcsji=w; /* 对称 */void kruskal(MGraph G)FILE *fpt;fpt = fopen("9.txt","w");/* 打开文档，写入 */fprintf(fpt,"最小生成树的各条边为:n");int i,j;int k=0,a=0,b=0 ,min=G.arcsab,m in _out;printf("最小生

17、成树的各条边为:n");while(k<G.vex num-1)for(i=0;i<G.vex nu m;+i)for(j=i+1;j<G.vex nu m;+j)if(G.arcsij<mi n)mi n=G.arcsij;a=i;b=j;min_out=mi n;min=G.arcsab=0x7fffffff;prin tf("%s-%s-%dn",G.vexsa,G.vexsb,min_out); fprin tf(fpt,"%s-%s-%dn",G.vexsa,G.vexsb,min_out); k+;fclos

18、e(fpt);void mai n()MGraph g;CreateGraph(&g); kruskal(g);4. 调试与操作说明4.1测试结果：如下图图2测试结果1图3测试结果24.2调试分析本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而调试比较顺利。在调试过程中主要是参数的传递比较不容易掌握。 本程序的关键部分是如何确定一条 边的两个端点是否属于同一连通分支，合并两个连通分支。5. 课程设计总结与体会5.1总结：克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满 足条件就将其构造，最后生成一个最小生成树。它首先是一系列的顶点集合，并 没有边，然后我们从邻接矩阵中寻找最小的边，看看