数据结构-kruskal算法求最小生成树 实验报告

最小生成树实验报告最小生成树实验报告一、引言最小生成树是图论中的一个重要概念，它在实际问题中有着广泛的应用。

本次实验旨在通过编程实现最小生成树算法，并通过实验数据对算法进行分析和评估。

二、算法介绍最小生成树算法的目标是在给定的带权无向图中找到一棵生成树，使得树上所有边的权重之和最小。

本次实验我们选择了两种经典的最小生成树算法：Prim 算法和Kruskal算法。

1. Prim算法Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展生成树的规模，直到包含所有顶点为止。

算法的具体步骤如下：（1）选择一个起始顶点，将其加入生成树中。

（2）从与生成树相邻的顶点中选择一个权重最小的边，将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法Kruskal算法是一种基于并查集的贪心算法，它首先将图中的边按权重从小到大进行排序，然后逐个加入生成树中，直到生成树包含所有顶点为止。

算法的具体步骤如下：（1）将图中的边按权重从小到大进行排序。

（2）逐个加入边，如果该边的两个顶点不在同一个连通分量中，则将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

三、实验过程本次实验我们使用C++语言实现了Prim算法和Kruskal算法，并通过随机生成的图数据进行了测试。

1. Prim算法的实现我们首先使用邻接矩阵表示图的结构，然后利用优先队列来选择权重最小的边。

具体实现过程如下：（1）创建一个优先队列，用于存储生成树的候选边。

（2）选择一个起始顶点，将其加入生成树中。

（3）将与生成树相邻的顶点及其边加入优先队列。

（4）从优先队列中选择权重最小的边，将其加入生成树中，并更新优先队列。

（5）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法的实现我们使用并查集来维护顶点之间的连通关系，通过排序后的边序列来逐个加入生成树中。

具体实现过程如下：（1）将图中的边按权重从小到大进行排序。

求最小生成树(Kruskal算法)实验报告一、实验目的通过本次实验，掌握Kruskal算法的基本原理，能够使用该算法求解最小生成树问题，并能够进行实际应用。

同时，为学习算法的设计和分析打下基础。

二、实验内容1. 理解Kruskal算法的基本原理。

2. 实现Kruskal算法，并将其应用于求解最小生成树问题。

3. 设计实验测试用例，验证程序正确性并进行性能分析。

三、实验原理Kruskal算法是最小生成树问题的一种解决方法。

该算法基于贪心策略，通过不断选择最短的边来构造最小生成树。

实现步骤如下：1. 将所有边按权重从小到大进行排序。

2. 遍历所有边，每次选择一条没有出现在生成树中的最短边，并将该边所连接的两个顶点合并到同一连通分量中。

3. 直到所有的边都被遍历过，即可得到最小生成树。

四、实验设计本次实验的主要任务是实现Kruskal算法，并运用到最小生成树问题中。

为了测试算法的正确性和性能，需要设计适当的测试用例。

具体的实验步骤如下：1. 设计数据结构在Kruskal算法中，需要维护边的信息，并对边进行排序，同时需要维护顶点的信息。

为方便实现，可以使用C++语言的STL库中的vector和set数据结构。

vector用于存储顶点信息，set用于存储排序后的边信息。

其中，顶点包含顶点编号和连通分量编号，边包含起点、终点和边权重。

为了方便生成测试数据，定义两个常量：MAX_VERTEX和MAX_EDGE。

MAX_VERTEX表示最大顶点数量，MAX_EDGE表示最大边数量。

2. 生成测试数据为了测试算法的正确性和性能，需要生成不同大小的测试数据。

可以随机生成若干个顶点和相应的边，其中顶点编号从1开始连续编号，边的起点和终点使用随机数生成，边的权重也使用随机数生成。

3. 实现Kruskal算法根据算法原理，可以实现基本的Kruskal算法。

具体实现过程如下：1. 首先将所有的边按照权重从小到大排序，并分别初始化每个顶点的连通分量编号。

最小生成树算法实验报告【实验报告】最小生成树算法实验一、实验目的本次实验旨在研究最小生成树算法，通过对比不同的算法，并对实验结果进行分析，探索最小生成树算法的优劣势和适应场景。

二、实验过程1.算法介绍本次实验中我们将使用两种最小生成树算法：普里姆算法和克鲁斯卡尔算法。

- 普里姆算法（Prim算法）：从一个顶点开始，不断在剩下的顶点中选择到当前已有的最小生成树的距离最小的边，将该边的另一个顶点加入树中，直到所有的顶点都加入树中。

- 克鲁斯卡尔算法（Kruskal算法）：首先将所有边按照权值从小到大进行排序，然后以最小权值的边开始，依次选择权值最小且不会形成环路的边，直到找到n-1条边为止，其中n为顶点数。

2.实验步骤首先，我们使用Python语言实现了普里姆算法和克鲁斯卡尔算法。

然后，我们构造了一些测试用例，包括不同规模的图和不同权值分布的图。

最后，我们对实验结果进行对比分析。

三、实验结果1.测试用例设计我们设计了三个测试用例，分别为小规模图、中规模图和大规模图，具体如下：-小规模图：顶点数为5的图，权值随机分布。

-中规模图：顶点数为50的图，权值随机分布。

-大规模图：顶点数为100的图，权值随机分布。

2.实验结果分析我们的实验结果如下表所示：算法，小规模图，中规模图，大规模图:-------:，:------:，:------:，:------:普里姆算法，13，455，703从实验结果可以看出，对于小规模图和中规模图，普里姆算法的运行时间明显低于克鲁斯卡尔算法。

但是对于大规模图，克鲁斯卡尔算法的运行时间与普里姆算法的运行时间差距不大，甚至略小于普里姆算法。

这是因为克鲁斯卡尔算法中排序边的时间复杂度为O(ElogE)，而普里姆算法中筛选最小距离的边的时间复杂度为O(V^2)。

综上所述，普里姆算法适用于较小规模的图，而克鲁斯卡尔算法适用于较大规模的图。

四、实验总结本次实验研究了最小生成树算法，通过对比实验结果，我们发现不同算法在不同规模的图上的表现有所差异。

摘要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的权值最小的生成树。

本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。

Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。

最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络等等一系列的应用。

关键词：最小生成树，邻接矩阵，Kruskal算法，Prim算法目录一、引言 (3)二、设计目的与任务 (4)2.1课程设计目的 (4)2.2课程设计的任务 (4)三、设计方案 (4)3.1需求分析 (4)3.2数据结构分析 (4)3.2.1抽象数据类型(ADT)如下 (4)3.2.2基本操作 (5)3.2.3存储结构 (5)3.3最小生成树的算法分析 (7)3.3.1主函数模块代码......................... 错误!未定义书签。

3.3.2邻接矩阵定义模块代码 (7)3.3.3创建链接矩阵模块代码 (7)3.3.4最小生成树Prim算法及代价模块代码...... 错误!未定义书签。

3.3.5最小生成树kruskal算法及代价模块代码 (8)四、调试分析与体会 (9)五、运行结果 (10)六、结论 (16)七、参考文献 (16)一、引言《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。

本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。

本课程设计我们要解决的问题是图最小生成树问题。

要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。

一、问题简述题目：图的操作。

要求：用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算法基本思路是：假设每个点都有一对标号 (d j, p j)，其中d j是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；p j则是从s到j的最短路径中j点的前一点。

求解从起源点s到点j的最短路径算法的基本过程如下：1) 初始化。

起源点设置为：① d s=0, p s为空;②所有其他点: d i=∞, p i=?;③标记起源点s，记k=s,其他所有点设为未标记的。

2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：d j=min［d j, d k+l kj］式中，l kj是从点k到j的直接连接距离。

3) 选取下一个点。

从所有未标记的结点中，选取d j中最小的一个i：d i=min［d j, 所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。

4) 找到点i的前一点。

从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5) 标记点i。

实验5 最小生成树算法的设计与实现一、实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。

二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。

有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。

设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。

三、Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53 4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U={}不属于最小生成树的顶点V={1，2，3，4，5，6}2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成四、实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； //定义比较方法x)；//在并查集森林中找到x的祖先int g etfa(intint s ame(int x,int y)； //判断祖先是否是同一个，即是否联通 void merge(int x,int y); //合并子树，即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M AXN_E 100000#define M AXN_V 100000using namespace std;struct Edge{int f m,to,dist;//边的起始顶点，边的到达顶点，边权}e[MAXN_E];int f a[MAXN_V],n,m; //顶点数组，顶点总数，边总数 //定义比较，只是边权比较bool cmp(Edge a,Edge b){return a.dist < b.dist;}//查找x的祖先是在并查集森林中找到x的祖先x){//getfaint g etfa(intreturn fa[x];if(fa[x]==x)else r eturn fa[x] = getfa(fa[x]);}//判断祖先是否是同一个，即是否联通int s ame(int x,int y){return getfa(x)==getfa(y);}//合并两棵树void merge(int x,int y){int f ax=getfa(x),fay=getfa(y);fa[fax]=fay;}int m ain(){int i;cout<<"请输入顶点数目和边数目："<<endl;cin>>n>>m;//n为点数，m为边数//输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i++){fa[i]=i;if(i!=0)cout<<fa[i]<<" ";}cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl;for(i=1;i<=m;i++)用边集数组存放边，方便排序和调用 cin>>e[i].fm>>e[i].to>>e[i].dist;//sort(e+1,e+m+1,cmp); //对边按边权进行升序排序表示目前的点共存在于多少个集合中，初始情况是每 int r st=n,ans=0;//rst个点都在不同的集合中for(i=1;i<=m && rst>1;i++){int x=e[i].fm,y=e[i].to;函数是查询两个点是否在同一集合中 if(same(x,y))continue;//sameelse{函数用来将两个点合并到同一集合中 merge(x,y);//mergerst--;//每次将两个不同集合中的点合并，都将使rst值减1这条边是最小生成树中的边，将答案加上边权 ans+=e[i].dist;//}}cout<<ans;return 0;}五、测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。

最小生成树Kruskal算法报告沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树Kruskal算法院（系）：计算机学院专业：计算机科学与技术目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (3)2.2.1 功能模块图 (3)2.2.2 流程图分析 (4)3 数据结构分析 (10)3.1存储结构 (10)3.2算法描述 (10)4 调试与分析 (13)4.1调试过程 (13)4.2程序执行过程 (13)参考文献 (16)附录（关键部分程序清单） (17)1 课程设计介绍1.1 课程设计内容设计程序，编写算法能建立带权图，并能够用Kruskal算法求该图的最小生成树，系统主要功能如下：1.最小生成树能够选择图上的任意一顶点做根结点；2.最小生成树输出不必采用图形方式，可按父结点和子女结点集的形式输出。

1.2 课程设计要求1.顶点信息用字符串，数据可自行设定；2.参考相应的资料，独立完成课程设计任务；3.交规范课程设计报告和软件代码。

2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为五大模块。

此五个模块相互联系，有嵌套调用的情况，以下是五个模块的大体分析：1.创建模块，建立无向连通图，创建图的总信息；2.发现模块，用Kruscal算法求最小生成树并调用search()函数;3.寻找模块，找出最小边(路径)，使各连通分量相统一，输出最小生成树对应边及对应结点并调用change()函数；4.改变模块，改变两个结点间的权值，使下一次寻找时不至于重复；5.选择模块，选择最小生成树的根结点并按父亲节点和子女结点的形式输出最小生成树。

2.2 原理图介绍2.2.1功能模块图图2.1功能模块图2.2.2 流程图分析1.创建模块，建立无向连通图，创建图的总信息，流程图如下：图2.2创建块流程图2.发现模块，用Kruscal算法求最小生成树并调用search()函数，流程图如下：图2.3发现模块流程图3.寻找模块，找出最小边(路径)，使各连通分量相统一，输出最小生成树对应边及对应结点并调用change()函数，具体流程图如下：图2.4寻找模块流程图图2.5寻找模块流程图4.改变模块，改变两个结点间的权值，使下一次寻找时不至于重复，具体流程图如下：图2.6改变模块流程图5.选择模块，选择最小生成树的根结点并按父亲节点和子女结点的形式输出最小生成树法，具体流程图如下：图2.7选择模块流程图3 数据结构分析3.1 存储结构定义结构体数组建立整个图的信息，包括图的各个结点的名称及对应的数字编号，连接两结点的边的权值，建立存在互相连通的两结点之间的联系且采用从头插入的链表连接方式，并且每个结点建立对应的邻接表，都采用头插入的方式，相互连接的两结点都存有对应的边的权值，存储代码如下：typedef struct link{int connect;//结点编号int fee;//权值struct link *next;}edgenode;typedef struct node{char name[10];//结点名称edgenode *link;}jiedian;typedef struct{jiedian vex[MAXSIZE];int jiedian_n,jiedian_e;//结点个数，边数(路径数)}jiedian_graph;3.2 算法描述1.建立两结点间联系，采用从头插入的方式，其中p,q分别为两项链结点的编号，简单算法说明如下：p->next=ga->vex[a].link;//建立两个结点间的联系ga->vex[a].link=p;q->next=ga->vex[b].link;ga->vex[b].link=q;2.寻找所建图中最小权值所在边对应的两个结点，如果寻找过则重新标记为一个统一的更大权值，以防止下次寻找时影响寻找的结果，简单算法说明如下：for(j=1;jjiedian_n+1;j++)//找权值最少的两个结点{p=ga->vex[j].link;//记下当前结点，以便在此结点的联系链中找到此链下的最小权值边(路径) while(p!=NULL){if((p->fee<min)&&(p->fee!=100))</min)&&(p->{min=p->fee;min_sign=p->connect;min_record=j;}p=p->next;}}3. 修改找到最小权值的边的权值，使其赋予更大的权值，简单算法说明如下：while(p!=NULL){if(p->connect==min_b)p->fee=100;q=p;p=p->next;}4.输出结点所连接的各个结点的的名称，运用啦信息表建立的头插入方式的邻接表，简单算法说明如下：while(p!=NULL){if(Mother[p->connect]!=0){printf("%s ",ga->vex[p->connect].name);Mother[p->connect]=0;}p=p->next;}4 调试与分析4.1 调试过程在调试程序是主要遇到一下几类问题：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++语言集成开发环境。

大连民族学院计算机科学与工程学院实验报告实验题目：最小生成树的Kruskal算法课程名称：离散数学实验类型：□演示性□验证性□操作性■设计性□综合性专业：软件工程班级：111学生姓名：xx学号：xx实验日期：2012年12月6-28日实验地点：金石滩校区机房201 实验学时：10学时实验成绩：指导教师：焉德军姜楠2012年12月28 日[实验原理]设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。

然后依次将这些边按所给图的结构放到生成树中去。

如果在放置某一条边时，使得生成树形成回路，则删除这条边。

这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。

[实验内容]给定无向连通加权图，编程设计求出其一棵最小生成树。

[实验目的]通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。

[实验步骤]（1）边依小到大顺序得l1，l2，…，lm。

（2）置初值：⇒∅S，0⇒i，1⇒j。

（3）若i=n-1，则转（6）。

（4）若生成树边集S并入一条新的边lj之后产生的回路，则j+1⇒j，并转（4）。

（5）否则，i+1⇒i；l j⇒S（i）；j+1⇒j，转（3）。

（6）输出最小生成树S。

（7）结束。

具体程序的C++实现如下：#include<iostream>using namespace std;const int MaxVertex = 20;const int MaxEdge = 100;const int MaxSize = 100;struct EdgeType{int from;int to;int weight;};struct EdgeGraph{char vertex[MaxVertex];EdgeType edge[MaxEdge];int vertexNum;int edgeNum;};int FindRoot(int parent[], int v);void InputInfo();void Kruskal(EdgeGraph G){int vex1,vex2,f,t;int i,num;int parent[MaxVertex];for(i=0; i<G.vertexNum; i++){parent[i] = -1;}for(num =0,i=0; i<G.edgeNum; i++){vex1 = FindRoot(parent, G.edge[i].from);vex2 = FindRoot(parent, G.edge[i].to);if(vex1 != vex2){cout << "(" << G.edge[i].from << "," << G.edge[i].to << ")" << endl;f = G.edge[i].from;t = G.edge[i].to;cout << "(" << G.vertex[f] << "," << G.vertex[t] << ")" << " Weight: " << G.edge[i].weight << endl;cout << endl;parent[vex2] = vex1;num++;if(num == G.vertexNum-1) return;}}return;}int FindRoot(int parent[], int v){int t;t = v;if(parent[t] > -1){t = parent[t];}return t;}void InputInfo(){EdgeGraph G;cout << "Please input vertexNum , edgeNum: " << endl;cin >> G.vertexNum >> G.edgeNum;cout << "Please input the information of edges:" << endl;for(int i=0; i<G.vertexNum; i++){cin >> G.vertex[i];}cout << "Please input this edge attaches two vertices subscript and its weight" << endl;for(int j=0; j<G.edgeNum; j++){cin >> G.edge[j].from >> G.edge[j].to >> G.edge[j].weight;}Kruskal(G);}int main(){InputInfo();system("pause");return 0;}实验过程中遇到的问题及解决过程比如不知道如何存储边集数组，以及比知道如何声明一些变量，函数和怎样去调用Kruskal函数……解决：通过设置结构体EdgeType与结构体EdgeGraph的联合来存储边集，因为在刚开始我在主函数中用EdgeGraph声明变量G，来作为形参去调用Kruskal(G)，编译时就会警告未被初始化的G，的程序出错，后来我将Kruskal(G)在InputInfo() 中调用，因为InputInfo()函数中声明了变量G，并使得G初始化，从而是的程序能正常运行。

数据结构实验报告最小生成树实验目的：掌握最小生成树的概念和算法，培养分析和解决实际问题的能力。

实验内容：利用Kruskal算法求解带权无向连通图的最小生成树。

实验原理：最小生成树是指一个连通图的生成树，其中所有边的权值和最小。

最小生成树问题在图论中有着重要的应用，如网络设计、集成电路布线等领域。

本次实验使用Kruskal算法求解最小生成树。

Kruskal算法基于一个贪心的思想：每次选择权值最小的边，直到生成树中包含所有的节点。

具体算法如下：1.根据给定的连通图构造一个边的集合E，E中包含图中所有的边。

2.将E中的边按照权值从小到大排序。

3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中。

4.重复第3步，直到生成树中包含所有的节点。

实验步骤及结果：1.根据给定的连通图构造边的集合E，并将E中的边按照权值从小到大排序。

2.初始化一个空的集合T作为最小生成树的边集合。

3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中，同时将该边添加到集合T中。

4.重复第3步，直到生成树中包含所有的节点。

实验结果分析：通过Kruskal算法，可以得到带权无向连通图的最小生成树。

最小生成树具有多个优点，如能够保证连通、权值最小、无回路。

在实际应用中，最小生成树常常用于网络设计、集成电路布线等领域。

实验总结：通过本次实验，我掌握了最小生成树的概念和Kruskal算法的原理和实现方法。

实验中，我通过定义边的数据结构和构造边的集合，实现了Kruskal算法求解最小生成树。

通过实验，我深刻认识到数据结构在解决实际问题中的重要性和实用性。

最小生成树作为一种常用的图论算法，在实际应用中具有广泛的应用和重要的价值。

掌握了最小生成树的概念和算法，我相信能够在今后的学习和工作中更好地应用数据结构算法解决实际问题。