下载文档原格式
最小生成树之克鲁斯卡尔(Kruskal)算法、普里姆(prim)算法分类：算法 2012-01-04 11:091159人阅读评论(0)收藏举报算法问题描述：在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，其中代价最小的生成树则称为最小生成树。
例如，设有下图G，找出连接图G所有顶点（v1,v2,v3,v4,v5,v6）的边，且这些边的权重之和最小。
那么如何生成该最小生成树呢？两个经典算法是普里姆 (Prim)算法和克鲁斯卡(Kruskal )算法。
克鲁斯卡尔（Kruskal)算法：克鲁斯卡尔(Kruskal)算法是以图上的边为出发点依据贪心策略逐次选择图中最小边为最小生成树的边，且所选的当前最小边与已有的边不构成回路。
在图G中，首先选择最小的边（V2,V3），（V4,V5），（V2,V4），因为（V4,V6）和（V5,V6）权重相等，所以可以任选其中一条（这也表明最小生成树不是唯一的）。
同样的道理，选择权重为5的边（V3,V5）（V2,V1），因为（V3,V5）和（V2,V3），（V2,V4），（V4,V5）构成了回路，所以舍弃（V3,V5）保留（V2,V1）。
这时该子图G‘已经包含了图G的所有的边，算法结束。
得到的最小生成树如下图：伪代码： Kruskal(G,W)1、按照权重从小到大顺序排序G的边{e1,e2,e3,e4,e5,...,em}；2、for i = 1to m do3、如果ei的两个端点不在同一个连通分支，则将ei加到T中；算法特点：时间复杂度为O(eloge)(e为网中边数)，适合于求稀疏的网的最小生成树。
普里姆（Prim)算法：普里姆（Prim)算法是以图上的顶点为出发点，逐次选择到最小生成树顶点集距离最短的顶点为最小生成树的顶点，并加入到该顶点集，直到包含所有的顶点。
在图G中，选择顶点V1加入到顶点集S，连接S中顶点的边为（V1,V2）（V1,V3），选择最小的即（V1,V2），并将V2加入到顶点集S。
最小生成树克鲁斯卡尔算法详解转载自：数据结构中图结构的最小生成树克鲁斯卡尔算法详解我一直想把克鲁斯卡尔算法实现，但是由于马上就要考试了，而且自己由于天气寒冷等各种原因没能如愿。
不过在昨天一天的努力中，我终于完成了克鲁斯卡尔算法的实现。
算法是c++的，图的数据结构是以邻接矩阵为基础，并且使用了模板，所以可以对任何类型的顶点进行最小生成树的生成。
克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件就将其构造，最后生成一个最小生成树。
它首先是一系列的顶点集合，并没有边，然后我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，则舍弃，另外取其它的边。
如果不连接成环，则接受这个边，并把其纳入集合中。
以此类推。
我们知道，一课有n个顶点的树(无论是树还是二叉树)，它必定有n-1个边。
我们只需要对上述操作循环至少n-1次(因为可能选出的边会构成环，不是我们需要的边)。
下面就是我寻找最小边的c++代码：Code：min=INFINITY；for(i=0；i vexnum；i++){for(j=i；j vexnum；j++){if(arcs[i][j].adj！=INFINITY&&minarcs[i][j].adj){if(arcs[i][j].adj=vexSet.lowcost&&！vexSet.IsAlreadyIn(i,j)){min=arcs[i][j].adj；track_i=i；track_j=j；}}}}首先让min为最大(INFINITY)，然后让其与邻接矩阵的一个个元素进行比较，我在遍历邻接矩阵的时候使用的是上三角(◥)法，因为无向网的邻接矩阵是对称矩阵。
当然我们必须记录满足调件的顶点的下标，所以track_i、track_j就变得必要了。
又因为我们要满足每次选取的最小权值的边呈递增数列，所以arcs[i][j].adj vexSet.lowcost(其中vexSet.lowcost为上次保存的最小边)就变得必要了。
最小生成树及克鲁斯卡尔算法
最小生成树是指在一个连通的无向图中，找到一棵生成树，使得所有
边的权值之和最小。
克鲁斯卡尔算法是一种用来求解最小生成树的贪
心算法。
克鲁斯卡尔算法的基本思想是将所有边按照权值从小到大排序，然后
依次加入生成树中，如果加入某条边会形成环，则不加入该边。
直到
生成树中有n-1条边为止，其中n为图中节点的个数。
克鲁斯卡尔算法的时间复杂度为O(ElogE)，其中E为边的数量。
因为需要对所有边进行排序，所以时间复杂度与边的数量有关。
最小生成树的应用非常广泛，例如在网络设计、电力传输、交通规划
等领域都有重要的应用。
在网络设计中，最小生成树可以用来构建网
络拓扑结构，使得网络的总成本最小。
在电力传输中，最小生成树可
以用来确定输电线路的布局，使得电力传输的成本最小。
在交通规划中，最小生成树可以用来确定道路的布局，使得交通运输的成本最小。
除了克鲁斯卡尔算法，还有其他求解最小生成树的算法，例如Prim算法、Boruvka算法等。
这些算法的基本思想都是贪心算法，但具体实
现方式有所不同。
总之，最小生成树是图论中的一个重要问题，克鲁斯卡尔算法是一种常用的求解最小生成树的算法。
在实际应用中，需要根据具体情况选择合适的算法，并结合实际需求进行优化。
荆楚理工学院课程设计成果学院:_______计算机工程学院__________ 班级: 14计算机科学与技术一班学生姓名: 陈志杰学号: 2014407020137设计地点（单位）_____B5101_________ ____________设计题目:克鲁斯卡尔算法求最小生成树__________________________________完成日期：2015年1月6日指导教师评语: ______________ ____________________________________________________________________________________________________________ ___________________________________________________________________________________________ ___________________________ __________ _成绩(五级记分制):_____ _ __________教师签名:__________ _______________注：介于A和C之间为B级，低于C为D级和E级。
按各项指标打分后，总分在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。
目录1 需求分析 (1)1.1系统目标 (1)1.2主体功能 (1)1.3开发环境 (1)2 概要设计 (1)2.1功能模块划分 (1)2.2 系统流程图 (2)3 详细设计 (3)3.1 数据结构 (3)3.2 模块设计 (3)4测试 (3)4.1 测试数据 (3)4.2测试分析 (4)5总结与体会 (6)5.1总结： (6)5.2体会： (6)参考文献 (7)附录全部代码 (8)1 需求分析1.1系统目标Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。
采用普里姆算法和克鲁斯卡尔算法,求最小生成树什么是最小生成树？最小生成树是图论中的一个重要概念，它是指在一个给定的无向连通图中，找到一棵树，使得这棵树连接图中的所有顶点，并且具有最小的权值总和。
最小生成树在很多实际问题中有着广泛的应用，比如城市规划、电力网络规划等。
普里姆算法：普里姆算法又称为“加点法”，它从一个初始随机点开始，逐渐往图中加入新的点，直到能够生成一棵包含所有节点的最小生成树。
1. 首先选择一个任意节点作为起始节点，加入最小生成树中。
2. 从已经加入最小生成树的节点中，选择一个与之相邻的节点并且不在最小生成树中的边，找到权值最小的边，将其加入最小生成树。
3. 重复第二步，直到最小生成树包含了所有的节点，即生成了一棵最小生成树。
克鲁斯卡尔算法：克鲁斯卡尔算法又称为“加边法”，它从原图的边集中选择权值最小的边，逐步加入生成树的边集中，直到遍历完所有的边，同时生成一棵最小生成树。
1. 首先把图中的所有边按照权值从小到大进行排序。
2. 依次遍历排序后的边，判断每一条边的两个顶点是否属于同一个连通分量。
3. 如果不属于同一个连通分量，将该边加入最小生成树的边集中，并将两个顶点所在的连通分量合并。
4. 重复第二步和第三步，直到遍历完所有的边或者最小生成树的边数达到图中节点数减一。
两种算法的比较：普里姆算法是从一个初始点开始，每次加入一个与最小生成树相连的具有最小权值的点，直到生成一棵最小生成树。
这种算法的时间复杂度为O(V^2)，其中V表示图中的顶点数。
因此，普里姆算法适用于顶点数较少的情况。
克鲁斯卡尔算法是将边按照权值排序后逐步加入最小生成树的边集中。
这种算法的时间复杂度为O(ElogE)，其中E表示图中的边数。
因此，克鲁斯卡尔算法适用于边数较少的情况。
从时间复杂度的角度来看，克鲁斯卡尔算法在边数较少的情况下更为高效，而普里姆算法在顶点数较少的情况下更为高效。
总结：最小生成树是一个在图论中非常重要且常用的概念，可以用于解决很多实际问题。
最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。
技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。
情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。
课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。
学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。
教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。
通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。
二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。
参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。
##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师: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算法。
该算法的主要步骤是：GENERNIC-MIT(G,W)1. A←2. while A没有形成一棵生成树3 do 找出A的一条安全边(u,v);4.A←A∪{(u,v)};5.return A算法设置了集合A，该集合一直是某最小生成树的子集。
在每步决定是否把边(u,v)添加到集合A中，其添加条件是A∪{(u,v)}仍然是最小生成树的子集。
我们称这样的边为A 的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。
然后就是Dijkstra算法。
Dijkstra算法基本思路是：假设每个点都有一对标号 (dj , pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。
求解从起源点s到点j的最短路径算法的基本过程如下：1) 初始化。
起源点设置为：① ds =0, ps为空;②所有其他点: di=∞, pi=?;③标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：d j =min［dj, dk+lkj］式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。
从所有未标记的结点中，选取dj中最小的一个i：di =min［dj, 所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。
从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5) 标记点i。
课程设计报告课程名称：数据结构课程设计设计题目：克鲁斯卡尔算法求最小生成树系别：计算机系专业：软件技术学生姓名：陈浩学号:************* 日期: 2013年1月5日 -2013年1月11日目录1. 需求分析 (2)1.1 设计题目 (2)1.2 设计任务及要求 (2)1.3课程设计思想 (2)1.4 程序运行流程: (2)1.5软硬件运行环境及开发工具 (2)2.概要设计 (2)2.1流程图 (2)2.2抽象数据类型MFSet的定义 (3)2.3主程序 (3)2.4抽象数据类型图的定义 (4)2.5抽象数据类型树的定义 (6)3. 详细设计 (8)3.1程序 (8)4.调试与操作说明 (11)4.1测试结果 (11)4.2调试分析 (12)5.课程设计总结与体会 (12)5.1总结 (12)5.2体会 (12)6. 致谢 (13)7. 参考文献 (13)1.需求分析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流程图图1流程图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是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。
}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定义构造图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中添加弧<v，w>，若G是无向的，则还增添对称弧<v，w>。
DeleteArc（&G，v，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抽象数据类型树的定义如下：ADT Tree{数据对象D:D是具有相同特性数据元素的集合。
数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱；（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，Dm（m>0），对任意j≠k（1≤j,k≤m）有Dj ∩Dk=Φ，且对任意的I（1≤i≤m），惟一存在数据元素xi∈Di 有<root，xi>∈H；（3）对应于D-{root}的划分，H-{<root，x1>，…，<roor，xm>}有惟一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k(1≤j，k≤m)有Hj∩Hk=Φ，且对任意I（1≤i≤m），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中某个结点，1≤i≤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程序：如下#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_NAME 5#define MAX_VERTEX_NUM 20typedef char Vertex[MAX_NAME];/*顶点名字串*/typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/typedef struct /*定义图*/{Vertex vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;} MGraph;typedef struct{Vertex adjvex; /*当前点*/int lowcost; /*代价*/}minside[MAX_VERTEX_NUM];int LocateVex(MGraph *G,Vertex u){int i;for(i=0;i<G->vexnum;++i)if(strcmp(G->vexs[i],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个顶点的值(<%d个字符):\n",G->vexnum,MAX_NAME);for(i=0;i<G->vexnum;++i) /* 构造顶点集*/scanf("%s",G->vexs[i]);for(i=0;i<G->vexnum;++i) /*初始化邻接矩阵*/for(j=0;j<G->vexnum;++j)G->arcs[i][j]=0x7fffffff;printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G->arcnum); for(k=0;k<G->arcnum;++k){scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G->arcs[i][j]=G->arcs[j][i]=w; /*对称*/}}void kruskal(MGraph G){int set[MAX_VERTEX_NUM],i,j;int k=0,a=0,b=0,min=G.arcs[a][b];for(i=0;i<G.vexnum;i++)set[i]=i;printf("最小代价生成树的各条边为:\n");while(k<G.vexnum-1){for(i=0;i<G.vexnum;++i)for(j=i+1;j<G.vexnum;++j)if(G.arcs[i][j]<min){min=G.arcs[i][j];a=i;b=j;}min=G.arcs[a][b]=0x7fffffff;if(set[a]!=set[b]){printf("%s-%s\n",G.vexs[a],G.vexs[b]);k++;for(i=0;i<G.vexnum;i++)if(set[i]==set[b])set[i]=set[a];}}}void main(){MGraph g;CreateGraph(&g);kruskal(g);system("PAUSE");getch();}4. 调试与操作说明4.1测试结果：如下图图2测试结果1图3测试结果24.2调试分析本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而条是比较顺利。
