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

…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………::任意创建一个图,利用克鲁斯卡尔算法,求出该图的最小生成树。:Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网,令T=(U,TE)是G的最小生成树。最短边策略从TE={}开始,每一次贪心选择都是在边集E中选择最短边(u,v),如果边(u,v)加入集合TE中不产生回路,则将边(u,v)加入边集TE中,并将它在集合E中删去。),它使生成树以一种任意的方式生长,先让森林中的树木随意生长,每生长一次就将两棵树合并,最后合并成一棵树。:1)提示输入顶点数目;2)接受输入,按照项目要求产生边权值的随机矩阵;然后求解最小生成树;3)输出最小生成树并且退出;::ADTMFSet{数据对象:若设S是MFSet型的集合,则它由n(n>0)个子集Si(i=1,2...,n)构成,每个子集的成员代表在这个子集中的城市。数据关系:S1US2US3U...USn=S,Si包含于S(i=1,2,...n)Init(n):初始化集合,构造n个集合,每个集合都是单成员,根是其本身。rank数组初始化0Find(x):查找x所在集合的代表元素。即查找根,确定x所在的集合,并路径压缩。Merge(x,y):检查x与y是否在同一个集合,如果在同一个集合则返回假,否则按秩合并这两个集合并返回真。}:intmain(){初始化;while(条件){接受命令;处理命令;}return0;}:ADTGraph{数据对象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定义构造图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是