下载文档原格式
数据结构课程设计最小生成树问题(总9页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--数据结构与算法课程设计报告课程设计题目：最小生成树问题专业班级：信息与计算科学1001班姓名：谢炜学号：4设计室号：理学院机房设计时间： 2011-12-26 批阅时间：指导教师：杜洪波成绩：一、摘要：随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社会生活的重要组成部分。
我们希望拥有一个宽松的上网环境，以便更好的进行信息的交流，在此我们有必要提升我们的网络传播速度。
从某种程度上来说网络传播速度代表着一个国家网络化程度的高低。
为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。
而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。
通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。
在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。
于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。
在原来的基础上建立一个带有权值的网络图。
于是原有的问题就转化为找图的最小生成树问题。
我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。
二、问题分析在n个城市间建立通信网络，需架设n-1条路线。
求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。
我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。
将城市之间的距离当做网中各点之间的权值。
三、实现本程序需要解决的问题（1）如何选择存储结构去建立一个带权的网络；（2）如何在所选存储结构下输出这个带权网络；（3）如何实现普利姆算法的功能；（4）如何从每个顶点开始找到所有的最小生成树的顶点；（5）如何输出最小生成树的边及其权值此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。
最小生成树1. 任务与需求该课程设计要求从从给定一个地图，包括若干城市间道路的距离，用Prim算法或者Kruskal算法建立最小生成树，求出最小生成树的代价。
用邻接矩阵来表示图。
根据分析，该课程设计需要完成的具体功能有：(1) 能够创建图；(2) 为了方便使用，可以把输入的图保存到数据文件中；(3) 能够读取数据文件中图的信息，创建图；(4) 能够显示最小生成树，包括起始和终点的序号以及最小生成树的代价。
图1 给定的图2. 总体设计对于一个无相连通图G=(V,E)，设G’是它的一个子图，如果G’满足下列条件：(1) G’中包含了G中所有顶点，即V(G’)=V(G)；(2) G’是连通图；(3) G’中无回路。
则称G’是G的一棵生成树。
如果无相连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，则称这棵生成树是最小代价生成树，简称为最小生成树。
最小生成树的概念可以应用到许多实际问题，例如：计算城市之间道路构造问题，要想使总的造价最低，实际上就是寻找该网络的最小生成树。
根据任务与需求，该程序需要能够输入数据、保存文件、读取文件、创建图、显示最小生成树。
最小生成树的常用算法有两种，分别使用这两种方法进行最小生成树的计算。
系统功能模块如图：图2 系统功能模块图3. 详细设计3.1 最小生成树算法常见的两种构造最小生成树的算法是Prim算法和Kruskal算法。
1. Prim算法假设G=(V,E)为一网络，其中V为网络中的顶点集合，E为网络中的所有带权边集合。
设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树的边。
令集合U的初值为U={u0}（假设从u0出发），集合T的初值为T={}。
从所有u∈U，v∈V-U两个顶点构成的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中。
如此不断重复，直到U=V时，最小生成树构造完毕，这时候集合T中包含了最小生成树的所有边。
武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：09计科2班学生姓名：蒋家权，陈相财，吴继伟，梁丽春指导教师：林丽惠完成日期：2011-1-19课程设计项目研究报告目录一、问题分析和任务定义....................................................................................... - 1 -二、实现本程序需要解决的问题如下................................................................... - 1 -三、测试数据........................................................................................................... - 2 -四、算法思想........................................................................................................... - 3 -五、模块划分........................................................................................................... - 4 -六、算法设计与分析............................................................................................... - 7 -七、源程序............................................................................................................. - 11 -八、测试数据......................................................................................................... - 14 -九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 -十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。
课程设计报告问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。
对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。
我们要选择一棵生成树，使总的耗费最小（1）需求分析：在N地建设网络保证连通即可求最小的架设方式，任务完成可分为两个部分：A 存储N中任意两地之间的权（采用邻接表，邻接矩阵）B 用prim和克鲁斯卡尔两种算法分别求出N地中最优架设方式即最小生成树。
C 按顺序输出生成树中各条边以及它们的权值。
（2）概要设计：程序分为两大部分 1 存储部分，2 算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。
Prim算法的思想：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u 0},TE={f}。
此步骤设立一个只有结点u 0的结点集U 和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。
2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。
此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。
找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。
这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。
3:如果U=V,则算法结束;否则重复步骤2。
可以把本步骤看成循环终止条件。
我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。
技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。
情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。
课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。
学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。
教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。
通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。
二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。
参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。
数据结构实验报告-最小生成树（精选5篇）第一篇：数据结构实验报告-最小生成树电子科技大学实验报告学生姓名：XXX 学号：20***指导教师：刘峤实验地点：信软楼306实验时间：5月17日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—图三、实验学时：4四、实验原理：Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。
其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。
然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。
若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
如教材153页的图4.21(a)所示，按照Kruskal 方法构造最小生成树的过程如图4.21 所示。
在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。
依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
五、实验目的：本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。
通过练习，加强对算法的理解，提高编程能力。
六、实验内容：（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。
七、实验器材（设备、元器件）：八、数据结构及程序#include #include #include typedefstruct {intvex;intgno;}TVex,*TpVex;typedefstruct {intvhead, vtail;intwght;intflag;}TEdge,*TpEdge;typedef struct{TpVex VexList;TpEdge EdgeList;int nvex, nedge;}TGraph, *TpGraph;void begin(TpGraph G){ int i;for(i=1;i<=G->nvex;i++){G->VexList[i-1].gno=i;G->EdgeList[i-1].flag=0;} } int findmin(TpGraph G){ int i,j;int minwght=G->EdgeList[0].wght;for(i=0,j=-1;inedge;i++){ PC机一台，装有C/C++语言集成开发环境。
《数据结构》课程设计报告课程名称：最小生成树课题负责人名（学号）:同组成员名单（角色）：指导教师：评阅成绩：评阅意见：提交报告时间：2011年12月19日最小生成树计算机科学与技术专业学生：指导老师：[摘要]选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树（简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法，其中多数算法利用了MST的性质。
关键词：最小生成树连通图普里姆算法克鲁斯卡尔算法 MST一、设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二、算法思想分析该设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。
根据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。
1.算法思想1)普里姆（Prim）算法思想a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；c)重复b)直到所有的节点出列。
2)克鲁斯卡尔（Kruskal）算法思想为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。
具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。
##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第 2 学期一、需求分析1.问题描述：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
存储结构采用多种。
求解算法多种。
该题目需要运用最小生成树来解决。
最小生成树的代价之和最小，所以是一种最经济的架设方法。
2.基本功能该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。
3.输入输出首先输入顶点的个数以及边的个数，格式如:4 6。
然后输入边的权值，格式如：a b 1。
输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。
最小生成树的格式为：<顶点名顶点名>权值。
二、概要设计1.设计思路：问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。
1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。
然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。
2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
2.数据结构设计：1.抽象数据类型如下：ADT Graph{ 数据对象 V：v是具有相同特征的数据元素的集合，称为顶点集。
数据关系 R：R={VR}VR={<v,w>|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧<v,w>的意义或信息}基本操作：1)GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。
操作条件：按V和VR的定义构造图G。
2）LocateVex（G,u）；初始条件：图G存在，u和G中顶点有相同的特征。
操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
数据结构实验报告最小生成树实验目的：掌握最小生成树的概念和算法，培养分析和解决实际问题的能力。
实验内容：利用Kruskal算法求解带权无向连通图的最小生成树。
实验原理：最小生成树是指一个连通图的生成树，其中所有边的权值和最小。
最小生成树问题在图论中有着重要的应用，如网络设计、集成电路布线等领域。
本次实验使用Kruskal算法求解最小生成树。
Kruskal算法基于一个贪心的思想：每次选择权值最小的边，直到生成树中包含所有的节点。
具体算法如下：1.根据给定的连通图构造一个边的集合E，E中包含图中所有的边。
2.将E中的边按照权值从小到大排序。
3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中。
4.重复第3步，直到生成树中包含所有的节点。
实验步骤及结果：1.根据给定的连通图构造边的集合E，并将E中的边按照权值从小到大排序。
2.初始化一个空的集合T作为最小生成树的边集合。
3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中，同时将该边添加到集合T中。
4.重复第3步，直到生成树中包含所有的节点。
实验结果分析：通过Kruskal算法，可以得到带权无向连通图的最小生成树。
最小生成树具有多个优点，如能够保证连通、权值最小、无回路。
在实际应用中，最小生成树常常用于网络设计、集成电路布线等领域。
实验总结：通过本次实验，我掌握了最小生成树的概念和Kruskal算法的原理和实现方法。
实验中，我通过定义边的数据结构和构造边的集合，实现了Kruskal算法求解最小生成树。
通过实验，我深刻认识到数据结构在解决实际问题中的重要性和实用性。
最小生成树作为一种常用的图论算法，在实际应用中具有广泛的应用和重要的价值。
掌握了最小生成树的概念和算法，我相信能够在今后的学习和工作中更好地应用数据结构算法解决实际问题。
实验三：Prim 最小生成树（验证性、4学时）一、 实验目的和要求●理解图的遍历●理解构造无向联通图的最小生成树的方法（Prim 算法实现）●能用Prim 算法构造最小生成树出来二、 实验内容和原理(1)实验内容：用Prim 算法构造一颗最小生成树(2) 实验原理：①从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树只有一个顶点。
②找出一个端点在生成树中另一端点在生成树外的所有边，并把权值最小的边连到同它所关联的另一个顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，任选一条。
③反复执行②，直到所有顶点都包含在生成树时为止。
三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP 中文操作系统 （2）Turbo C 3.0四、 算法描述及实验步骤1、算法描述为了实现Prim 算法。
需设一个辅助数组closedge 来记录每次选择的权值最小的边。
数组元素closedge[i]对应于序号为i 的顶点v i ，它包含两个域adjvex 和lowcost 。
若v i 已在生成树上，则置closedge[i].lowcost=0;若顶点v i 不在生成树上，用closedge[i].low cost 存放v i 与生成树上的顶点构成的最小代价边的权值，而用closedge[i].adjvex 存放该边所关联的生成树上的另一顶点的序号。
2、算法流程图begin typedef struct ArcCellvoid CreateGraph(MGraph &G) hand !=110 1113、代码(注释)#include <stdio.h>#include <stdlib.h>#include <iostream.h>#define INFINITY INT_MAX tide != G .vexs[k] G .arcs[j][k].adj = weigh; G .arcs[k][j].adj = weigh; j = 0;k = 0;void MiniSpanTree_PRIM(MGraph G ,V erTexType u) j<G .vexnum G .arcs[k][j].adj < close[j].lowcostclose[j].adjvex = G .vexs[k]; close[j].lowcost= G .arcs[k][j].adj;j++ j++j=0i++int LocateV ex(MGraph G , V erTexType u) end int minimum(closedgeclose)#define MAX_VERTEX_NUM 20 //最大顶点数为20//typedef int VRType;typedef int InfoType;typedef char V erTexType;typedef struct ArcCell // 邻接矩阵定义//{VRType adj;InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{V erTexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum, arcnum; }MGraph;typedef struct //记录从顶点集U到V-U的代价最小的边的辅助数组定义//{ V erTexType adjvex;VRType lowcost;}closedge[MAX_VERTEX_NUM];void CreateGraph(MGraph &G); //建立无向图//void MiniSpanTree_PRIM(MGraph G, V erTexType u);//用Prim算法从第u个顶点出发构造无向连通网G的最小生成树T//int LocateV ex(MGraph G, V erTexType u);//求顶点在图中的位置//int minimum(closedge close);//最小边的权重//void main( void ){int i, j;MGraph G;cout<<"==================用Prim算法求最小生成树==================="<<endl; CreateGraph(G);//调用CreateGraph(G)建立图//cout<<"程序所建立的图的邻接矩阵如下所示:"<<endl;cout<<"-------------------------------------";cout<<endl<<" ";for(i = 0; i < G.vexnum; i++){cout<<G.vexs[i]<<" ";}cout<<endl;for(i = 0; i < G.vexnum; i++){cout<<G.vexs[i]<<" ";for(j = 0; j < G.vexnum; j++){cout<<G.arcs[i][j].adj;cout<<" ";}cout<<endl;}cout<<"-------------------------------------"<<endl;MiniSpanTree_PRIM(G,'a');}void CreateGraph(MGraph &G)//构造无向连通网G//{int weigh;//weigh变量为图中结点的权重//int i, j = 0, k = 0;char hand, tide;cout<<"请您输入所建图中的结点的个数the number for vexnum:";cin>>G.vexnum;cout<<"请您输入所建图中的各结点间的连接的边数(最大边数为"<<G.vexnum*G.vexnum<<")the number for arcnum:";cin>>G.arcnum;for(i = 0; i < G.vexnum; i++){for(j = 0; j < G.vexnum; j++)G.arcs[i][j].adj = 99; }//图中两个结点不相联，权值定为99//cout<<endl;cout<<"请您输入"<<G.vexnum<<"(char)型的字符作为图中的结点名称:"<<endl;for(i=0; i < G.vexnum; i++){cin>>G.vexs[i];}cout<<endl;cout<<"请您输入"<<G.vexnum<<"(char)型的字符作为图中的结点名称:"<<endl;for(i=0; i < G.arcnum; i++){cout<<i+1<<":";cin>>hand;cin>>tide;cin>>weigh;while (hand != G.vexs[j]){j++;}while (tide != G.vexs[k]){k++;}G.arcs[j][k].adj = weigh;G.arcs[k][j].adj = weigh;j = 0;k = 0;}cout<<endl;}void MiniSpanTree_PRIM(MGraph G,V erTexType u)//用Prim算法从第u个顶点出发构造网G 的最小生成树T，输出它的各条边并算出//{int i, j, k = 0;closedge close;k = LocateV ex ( G, u );for ( j = 0; j < G.vexnum; j++ )//辅助数组初始化//{if (j != k){close[j].adjvex = G.vexs[k];close[j].lowcost = G.arcs[k][j].adj;}}close[j].lowcost = 99;close[j].adjvex = '\0';close[k].lowcost = 0;close[k].adjvex = u;cout<<"用Prim算法实现的程序求得的最小生成树如下所示:"<<endl;for (i = 1; i < G.vexnum; i++)//选择其余G.vexnum-1个顶点//{k = minimum(close); //求出T的下一个结点：第k个顶点//cout<<close[k].adjvex; //输出生成树的边//cout<<"---->";cout<<G.vexs[k]<<" ";cout<<close[k].lowcost<<endl;close[k].lowcost = 0; //第k顶点并入U集//for (j=0; j<G.vexnum; j++){if (G.arcs[k][j].adj < close[j].lowcost)//新顶点并入U集后重新选择最小边//{close[j].adjvex = G.vexs[k];close[j].lowcost = G.arcs[k][j].adj;} } } }int LocateV ex(MGraph G, V erTexType u)//求顶点在图中的位置//{int k = 0;while(G.vexs[k++] == u)return k-1;return 0;}//若G中存在顶点u则返回该顶点在图中的位置，否则返回-1//int minimum(closedge close)//最小边的权重//{int j1=0, client = 99, j2;while(close[j1].adjvex != '\0'){if (client > close[j1].lowcost && close[j1].lowcost != 0){client = close[j1].lowcost;j2 = j1;}j1++;}return j2;}五、调试过程出错原因：语句“InfoType ->info;”出错，只要把“InfoType ->info;”改为即“InfoType *info;”即可。
数据结构实验最小生成树数据结构实验报告最小生成树问题一、问题描述:若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题基本要求(1)从文件中读入图的信息。
(2)利用克鲁斯卡尔算法求网的最小生成树。
(3)以文本形式生成树中各条边以及他们的权值。
二(需求分析:1、需定义结构体数组，根据权值逐一选择边。
三(概要设计抽象数据类型:需定义结构体数组，存储每条边的起点，终点，权值。
算法的基本思想:1、图的信息的读取:定义结构体数组，存储每条边的起点，终点，权值。
2、对每条边在数组中的位置处理:选边需从最小的开始，故按边的权值从小到大进行排序。
3、边的选取: 从最小的边的开始，若边的两端点不属于同一集合，则选取该边。
并将该边的两个顶点所在的两个集合合并成为一个。
因为有n个顶点，故只需选取n-1条边。
程序的流程:(1) 输入模块: 读入图的信息(顶点和边，用结构体数组进行存储)。
(2) 处理模块:Kruskal算法。
(3) 输出模块:将结果输出。
四(详细设计:算法的具体步骤:struct G{int fromvex;int endvex;int weight;}GE[100],cur[100];void swap(G* GE,int i,int j){ //交换函数int temp=GE[i].fromvex;GE[i].fromvex=GE[j].fromvex;GE[j].fromvex=temp;temp=GE[i].endvex;GE[i].endvex=GE[j].endvex;GE[j].endvex=temp;temp=GE[i].weight;GE[i].weight=GE[j].weight;GE[j].weight=temp;}void Kruskal(int n){int i,j,k=0,pos=-1,m1,m2;bool** s=new bool *[n];//定义一个二维数组，用来判断是否为同一类for(i=0;i<n;i++)s[i]=new bool[n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=true; //初始化数组elses[i][j]=false;}}while(k<n-1){for(i=0;i<n;i++){if(s[i][GE[k].fromvex]==1)m1=i;if(s[i][GE[k].endvex]==1)m2=i;}if(m1!=m2){//判断是否为同一类,如果为同一类(该类中所有的点到起点和终//点的边在s 数组中赋为1)，cur[++pos].fromvex=GE[k].fromvex;cur[pos].endvex=GE[k].endvex;cur[pos].weight=GE[k].weight;for(i=0;i<n;i++){if(s[m1][i] || s[m2][i])//把该点添加到该类，并和并两个类s[m1][i]=1;elses[m1][i]=0;s[m2][i]=0;}}k++;}for(i=0;i<n;i++){delete []s[i];}}int main(){int i,j;int numVertex,numEdge;cout<<"请输入点的个数和边的条数:"<<endl; cin>>numVertex>>numEdge;cout<<"请输入边的起始位置和边的权值:"<<endl;for(i=0;i<numEdge;i++)cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;for(i=0;i<numEdge;i++)for(j=i;j<numEdge;j++){if(GE[j].weight<GE[i].weight)//将边的权值按从小到大排列swap(GE,i,j);}Kruskal(numEdge);for(i=0;i<numVertex-1;i++) cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;system("pause");return 0;}五(调试分析:将选边的过程输出来检验算法的正确性。
数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名: XXX班级： XXX 学号: XXXXXXXXX起迄日期: 2015.07.13-2015.07.24指导教师: XXX XXX任务书最小生成树问题[问题描述]在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
[设计要求]（1）通过输入建立一无向网，存储结构可以采用多种；（2）要求分别采用普里姆算法和克鲁斯卡尔算法实现；（3）若以图形界面输出可以适当加分。
一、需求分析1.问题描述：该程序主要实现最小生成树功能，在给定的中国铁路网中，选择城市，生成最小生成树。
此外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离等图论的基本操作。
直观、清晰的为用户提供全国铁路网的最基本情况。
该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。
输入指定的城市求出最小生成树，方便查询城市间的最短连通量。
另外添加了显示全国主要铁路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介绍。
该程序实现了指定城市到其它城市之间的最短距离。
通过在地图上选择城市，程序通过Dijkstra算法计算出指定城市到其它城市之间的最短距离，并通过textBox控件显示，一目了然。
具有较强的人机和谐性。
还可以实现指定城市之间的最短路，输入两个指定的城市，通过Floyd算法求出选定城市间的最短距离。
并在图形界面上标注要经过的城市。
2.基本功能：（1）通过输入建立一无向网，存储结构采用了邻接矩阵。
（2）要求分别采用Prim算法和Kruskal算法实现，分别对应Prim.cs和Kruskal.cs。
（3）若以图形界面输出会适当加分。
3.附加功能：（1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介绍。
主要实现代码在Map.cs中。
（2）指定城市到其它城市的最短距离，在地图上点击指定城市，程序会显示指定城市到其它城市的最短距离。
(此文档为word格式，下载后您可任意编辑修改！) 课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树Kruskal算法院（系）：专业：班级：学号：姓名：指导教师：目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (4)2.2.1 功能模块图 (4)2.2.2 流程图分析 (5)3 数据结构分析 (11)3.1存储结构 (11)3.2算法描述 (11)4 调试与分析 (13)4.1调试过程 (13)4.2程序执行过程 (13)参考文献 (16)附录（关键部分程序清单） (17)1 课程设计介绍1.1 课程设计内容编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。
最小生成树能够选择图上的任意一点做根结点。
最小生成树输出采用顶点集合和边的集合的形式。
1.2 课程设计要求1.顶点信息用字符串，数据可自行设定。
2.参考相应的资料，独立完成课程设计任务。
3.交规范课程设计报告和软件代码。
2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。
以下是三个模块的大体分析：1.要确定图的存储形式，通过对题目要求的具体分析。
发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。
2.Kruskal算法。
该算法设置了集合A，该集合一直是某最小生成树的子集。
在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。
我们称这样的边为A 的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。
3.Dijkstra算法。
算法的基本思路是：假设每个点都有一对标号（d j,p j）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j则是从s到j的最短路径中j点的前一点。
最小生成树课程设计一、课程目标知识目标：1. 学生能够理解最小生成树的概念，掌握其定义和性质；2. 学生能够掌握两种常见的最小生成树算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法；3. 学生能够运用最小生成树解决实际问题，如网络设计、电路设计等。
技能目标：1. 学生能够运用图论知识，分析并解决最小生成树问题；2. 学生能够编写和调试实现最小生成树的算法程序；3. 学生能够通过小组合作，共同探讨并解决最小生成树相关问题。
情感态度价值观目标：1. 学生通过学习最小生成树，培养对图论的兴趣，激发探索数学问题的热情；2. 学生在合作解决问题的过程中，学会沟通、协作，培养团队精神；3. 学生能够认识到数学知识在实际生活中的广泛应用，增强学习的积极性和主动性。
课程性质：本课程为计算机科学、信息技术等相关专业的高年级学生设计，旨在帮助学生掌握最小生成树的基本原理和算法，提高解决实际问题的能力。
学生特点：学生已经具备一定的图论基础，熟悉基本的算法和数据结构，具有一定的编程能力。
教学要求：通过讲解、示例、练习和小组讨论等形式，使学生掌握最小生成树的相关知识，提高编程实践能力和解决问题的能力。
同时，注重培养学生的团队合作精神和数学思维。
二、教学内容1. 最小生成树概念与性质- 定义、性质和判定条件- 最小生成树的应用场景2. 普里姆（Prim）算法- 算法原理与步骤- 代码实现与调试- 算法性能分析3. 克鲁斯卡尔（Kruskal）算法- 算法原理与步骤- 代码实现与调试- 算法性能分析4. 最小生成树算法比较与应用- 普里姆与克鲁斯卡尔算法的优缺点对比- 实际问题中的应用案例分析5. 小组讨论与练习- 分组讨论最小生成树相关算法及应用- 编写和调试最小生成树算法程序- 解决实际问题，如网络设计、电路设计等教学内容安排与进度：第一周：最小生成树概念与性质，普里姆算法原理与实现第二周：普里姆算法性能分析，克鲁斯卡尔算法原理与实现第三周：克鲁斯卡尔算法性能分析，最小生成树算法比较与应用第四周：小组讨论与练习，解决实际问题教材章节：《离散数学及其应用》第6章：图论《数据结构与算法分析》第9章：图论算法《计算机算法设计与分析》第4章：最小生成树与最短路径三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言、形象的比喻和具体的案例，讲解最小生成树的概念、性质和算法原理，使学生系统掌握理论知识。
数据结构（三⼗三）最⼩⽣成树（Prim、Kruskal） ⼀、最⼩⽣成树的定义 ⼀个连通图的⽣成树是⼀个极⼩的连通⼦图，它含有图中全部的顶点，但只有⾜以构成⼀棵树的n-1条边。
在⼀个⽹的所有⽣成树中，权值总和最⼩的⽣成树称为最⼩代价⽣成树（Minimum Cost Spanning Tree），简称为最⼩⽣成树。
构造最⼩⽣成树的准则有以下3条：只能使⽤该图中的边构造最⼩⽣成树当且仅当使⽤n-1条边来连接图中的n个顶点不能使⽤产⽣回路的边 对⽐两个算法，Kruskal算法主要是针对边来展开，边数少时效率会⾮常⾼，所以对于稀疏图有很⼤的优势；⽽Prim算法对于稠密图，即边数⾮常多的情况会更好⼀些。
⼆、普⾥姆（Prim）算法 1.Prim算法描述 假设N={V,{E}}是连通⽹，TE是N上最⼩⽣成树中边的集合。
算法从U={u0，u0属于V}，TE={}开始。
重复执⾏下⾯的操作：在所有u属于U，v 属于V-U的边(u,v)中找⼀条代价最⼩的边(u0,v0)并加⼊集合TE，同时v0加⼊U，直到U=V为⽌。
此时TE中必有n-1条边，则T=(V,{TE})为N的最⼩⽣成树。
2.Prim算法的C语⾔代码实现/* Prim算法⽣成最⼩⽣成树 */void MiniSpanTree_Prim(MGraph G){int min, i, j, k;int adjvex[MAXVEX]; /* 保存相关顶点下标 */int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */lowcost[0] = 0;/* 初始化第⼀个权值为0，即v0加⼊⽣成树 *//* lowcost的值为0，在这⾥就是此下标的顶点已经加⼊⽣成树 */adjvex[0] = 0; /* 初始化第⼀个顶点下标为0 */for(i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i]; /* 将v0顶点与之有边的权值存⼊数组 */adjvex[i] = 0; /* 初始化都为v0的下标 */}for(i = 1; i < G.numVertexes; i++){min = INFINITY; /* 初始化最⼩权值为∞， *//* 通常设置为不可能的⼤数字如32767、65535等 */j = 1;k = 0;while(j < G.numVertexes) /* 循环全部顶点 */{if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值⼩于min */{min = lowcost[j]; /* 则让当前权值成为最⼩值 */k = j; /* 将当前最⼩值的下标存⼊k */}j++;}printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最⼩的边 */lowcost[k] = 0;/* 将当前顶点的权值设置为0,表⽰此顶点已经完成任务 */for(j = 1; j < G.numVertexes; j++) /* 循环所有顶点 */{if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]){/* 如果下标为k顶点各边权值⼩于此前这些顶点未被加⼊⽣成树权值 */lowcost[j] = G.arc[k][j];/* 将较⼩的权值存⼊lowcost相应位置 */adjvex[j] = k; /* 将下标为k的顶点存⼊adjvex */}}}}Prim算法 3.Prim算法的Java语⾔代码实现package bigjun.iplab.adjacencyMatrix;/*** 最⼩⽣成树之Prim算法*/public class MiniSpanTree_Prim {int lowCost; // 顶点对应的权值public CloseEdge(Object adjVex, int lowCost) {this.adjVex = adjVex;this.lowCost = lowCost;}}private static int getMinMum(CloseEdge[] closeEdges) {int min = Integer.MAX_VALUE; // 初始化最⼩权值为正⽆穷int v = -1; // 顶点数组下标for (int i = 0; i < closeEdges.length; i++) { // 遍历权值数组，找到最⼩的权值以及对应的顶点数组的下标if (closeEdges[i].lowCost != 0 && closeEdges[i].lowCost < min) {min = closeEdges[i].lowCost;v = i;}}return v;}// Prim算法构造图G的以u为起始点的最⼩⽣成树public static void Prim(AdjacencyMatrixGraphINF G, Object u) throws Exception{// 初始化⼀个⼆维最⼩⽣成树数组minSpanTree，由于最⼩⽣成树的边是n-1，所以数组第⼀个参数是G.getVexNum() - 1，第⼆个参数表⽰边的起点和终点符号，所以是2 Object[][] minSpanTree = new Object[G.getVexNum() - 1][2];int count = 0; // 最⼩⽣成树得到的边的序号// 初始化保存相关顶点和相关顶点间边的权值的数组对象CloseEdge[] closeEdges = new CloseEdge[G.getVexNum()];int k = G.locateVex(u);for (int j = 0; j < G.getVexNum(); j++) {if (j!=k) {closeEdges[j] = new CloseEdge(u, G.getArcs()[k][j]);// 将顶点u到其他各个顶点权值写⼊数组中}}closeEdges[k] = new CloseEdge(u, 0); // 加⼊u到⾃⾝的权值0for (int i = 1; i < G.getVexNum(); i++) { // 注意，这⾥从1开始，k = getMinMum(closeEdges); // 获取u到数组下标为k的顶点的权值最短minSpanTree[count][0] = closeEdges[k].adjVex; // 最⼩⽣成树第⼀个值为uminSpanTree[count][1] = G.getVexs()[k]; // 最⼩⽣成树第⼆个值为k对应的顶点count++;closeEdges[k].lowCost = 0; // 下标为k的顶点不参与最⼩权值的查找了for (int j = 0; j < G.getVexNum(); j++) {if (G.getArcs()[k][j] < closeEdges[j].lowCost) {closeEdges[j] = new CloseEdge(G.getVex(k), G.getArcs()[k][j]);}}}System.out.print("通过Prim算法得到的最⼩⽣成树序列为: {");for (Object[] Tree : minSpanTree) {System.out.print("(" + Tree[0].toString() + "-" + Tree[1].toString() + ")");}System.out.println("}");}} 4.举例说明Prim算法实现过程 以下图为例： 测试类：// ⼿动创建⼀个⽤于测试最⼩⽣成树算法的⽆向⽹public static AdjacencyMatrixGraphINF createUDNByYourHand_ForMiniSpanTree() {Object vexs_UDN[] = {"V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"};int arcsNum_UDN = 15;int[][] arcs_UDN = new int[vexs_UDN.length][vexs_UDN.length];for (int i = 0; i < vexs_UDN.length; i++) // 构造⽆向图邻接矩阵for (int j = 0; j < vexs_UDN.length; j++)if (i==j) {arcs_UDN[i][j]=0;} else {arcs_UDN[i][j] = arcs_UDN[i][j] = INFINITY;}arcs_UDN[0][5] = 11;arcs_UDN[1][2] = 18;arcs_UDN[1][6] = 16;arcs_UDN[1][8] = 12;arcs_UDN[2][3] = 22;arcs_UDN[2][8] = 8;arcs_UDN[3][4] = 20;arcs_UDN[3][6] = 24;arcs_UDN[3][7] = 16;arcs_UDN[3][8] = 21;arcs_UDN[4][5] = 26;arcs_UDN[4][7] = 7;arcs_UDN[5][6] = 17;arcs_UDN[6][7] = 19;for (int i = 0; i < vexs_UDN.length; i++) // 构造⽆向图邻接矩阵for (int j = i; j < vexs_UDN.length; j++)arcs_UDN[j][i] = arcs_UDN[i][j];return new AdjMatGraph(GraphKind.UDN, vexs_UDN.length, arcsNum_UDN, vexs_UDN, arcs_UDN);}public static void main(String[] args) throws Exception {AdjMatGraph UDN_Graph = (AdjMatGraph) createUDNByYourHand_ForMiniSpanTree();MiniSpanTree_Prim.Prim(UDN_Graph, "V0");} 输出为：通过Prim算法得到的最⼩⽣成树序列为: {(V0-V1)(V0-V5)(V1-V8)(V8-V2)(V1-V6)(V6-V7)(V7-V4)(V7-V3)} 分析算法执⾏过程：从V0开始：-count为0，k为0，closeEdges数组的-lowCost为{0 10 INF INF INF 11 INF INF INF}，adjVex数组为{V0，V0，V0，V0，V0，V0，V0，V0，V0}-⽐较lowCost，于是k为1，adjVex[1]为V0，minSpanTree[0]为（V0，V1），lowCost为{0 0 INF INF INF 11 INF INF INF}-k为1，与V1的权值⾏⽐较，得到新的-lowCost为：{0 0 18 INF INF 11 16 INF 12}，adjVex数组为{V0，V0，V1，V0，V0，V0，V1，V0，V1}-⽐较lowCost，于是k为5，adjVex[5]为V0，minSpanTree[1]为（V0，V5），lowCost为{0 0 18 INF INF 0 16 INF 12}-k为5，与V5的权值⾏⽐较，得到新的-lowCost为{0 0 18 INF 26 0 16 INF 12}，adjVex数组为{V0，V0，V1，V0，V5，V0，V1，V0，V1}-⽐较lowCost，于是k为8，adjVex[8]为V1，minSpanTree[2]为（V1，V8），lowCost为{0 0 18 INF INF 0 16 INF 0}... 三、克鲁斯卡尔（Kruskal）算法 1.Kruskal算法描述 Kruskal算法是根据边的权值递增的⽅式，依次找出权值最⼩的边建⽴的最⼩⽣成树，并且规定每次新增的边，不能造成⽣成树有回路，直到找到n-1条边为⽌。
《数据结构》期末课程设计题目第8题：最小生成树问题学院计算机学院专业班别学号姓名陈聪2015年7月6日一、需求分析1、问题描述若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。
2、基本要求（1）利用克鲁斯卡尔算法求网的最小生成树。
（2）实现并查集。
以此表示构造生成树过程中的连通分量。
（3）以文本形式输出生成树中各条边以及他们的权值。
3、实现提示通讯线路一旦建立，必然是双向的。
因此，构造最小生成树的网一定是无向网。
设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。
图的存储结构的选取应和所作操作向适应。
为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。
二、详细设计根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。
1、边集数组的类型定义：typedef struct{int x, y;int w;}edge;x表示起点，y表示终点，w为权值。
2、并查集功能的实现由以下函数实现：Make_Set(int x)初始化集合；Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径；Union(int x, int y, int w)合并x,y所在的集合。
3、克鲁斯卡尔算法的实现该算法的实现位于主函数中：qsort(e, n, sizeof(edge), cmp); //将边排序printf("最小生成树的各条边及权值为：\n");for (i = 0; i < n; i++){x = Find_Set(e[i].x);y = Find_Set(e[i].y);if (x != y ){printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);Union(x, y, e[i].w);}}4、设计中还包含以下函数：（1）/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b){if ((*(edge *)a).w == (*(edge *)b).w){return (*(edge *)a).x - (*(edge *)b).x;}return (*(edge *)a).w - (*(edge *)b).w;}（2）快排函数qsort,包含在stdlib.h头文件里qsort(e, n, sizeof(edge), cmp);（3）C语言提供的随机数函数srand( unsigned int seed );使用随机数函数如下：srand( (unsigned)time( NULL ) );for( i = 0; i < n;i++ ){e[i].w=rand()%100+1;e[i].x = chx - 'A';if(chy==h+48) chx++;e[i].y = (chy++) - 'A';if(chy==h+49) chy=chx+1;Make_Set(i);}输出1～100之间的随机数，使用rand()%100+1。
5 Array三、调试分析调试过程中遇到的问题：随机产生权值时，通过边数不能确定起点和终点。
解决：通过顶点数对所有边取随机数。
四、用户使用说明及测试结果1、打开界面：（1）人为输入权值，输入1，回车：输入7，回车：输入边的信息及结果如下：（2）随机生成权值，输入0：输入顶点数5，结果如下：五、经验和体会通过本次课程设计，我学会了利用克鲁斯卡尔算法求最小生成树。
另外学会了利用随机函数产生随机数，以及课本没有提到的边集数组的定义和使用。
六、附录源代码#include <stdio.h>#include <stdlib.h>#include "time.h"#define MAX 435/* 定义边(x,y)，权为w */typedef struct{int x, y;int w;}edge;edge e[MAX];/* rank[x]表示x的秩*/int rank[MAX];/* father[x]表示x的父节点*/int father[MAX];/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b){if ((*(edge *)a).w == (*(edge *)b).w){return (*(edge *)a).x - (*(edge *)b).x;}return (*(edge *)a).w - (*(edge *)b).w;}/* 初始化集合*/void Make_Set(int x){father[x] = x;rank[x] = 0;}/* 查找x元素所在的集合,回溯时压缩路径*/int Find_Set(int x){while(father[x]){x=father[x];}return x;}/* 合并x,y所在的集合*/void Union(int x, int y, int w){if (x == y) return;/* 将秩较小的树连接到秩较大的树后*/if (rank[x] > rank[y]){father[y] = x;}else{if (rank[x] == rank[y]){rank[y]++;}father[x] = y;}}/* 主函数*/int main(){printf("*最小生成树问题：\n");int i, n,h,k=0;int x, y;char chx, chy;printf("\n人为输入权值请输入1，随机生成权值请输入0：\n");scanf("%d",&k);if(k==1){/* 读取边的数目*/printf("请输入边的条数（小于436）:\n");scanf("%d", &n);getchar();/* 读取边信息并初始化集合*/printf("请输入边的信息（起点，终点，权值(<100)）分别用空格隔开:\n");for (i = 0; i < n; i++){scanf("%c %c %d", &chx, &chy, &e[i].w);getchar();e[i].x = chx - 'A';e[i].y = chy - 'A';Make_Set(i);}}else{printf("请输入顶点数（<=30）:\n");scanf("%d", &h);getchar();srand( (unsigned)time( NULL ) );n=(h-1)*h/2;chx=49;chy=50;for( i = 0; i < n;i++ ){e[i].w=rand()%100+1;e[i].x = chx - 'A';if(chy==h+48) chx++;e[i].y = (chy++) - 'A';if(chy==h+49) chy=chx+1;Make_Set(i);}printf("随机生成的各条边及权值为：\n");for (i = 0; i < n; i++){printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);}}/* 将边排序*/qsort(e, n, sizeof(edge), cmp);printf("最小生成树的各条边及权值为：\n");for (i = 0; i < n; i++){x = Find_Set(e[i].x);y = Find_Set(e[i].y);if (x != y ){printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);Union(x, y, e[i].w);}}return 0;}。
