数据结构实验报告-最小生成树

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

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

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

本次实验我们选择了两种经典的最小生成树算法：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）将图中的边按权重从小到大进行排序。

最小生成树（Minimum Spanning Tree）实验报告1. 实验目的本实验旨在通过实践掌握最小生成树算法的基本原理和实现方法。

最小生成树是图论中的一个重要概念，用于解决具有权重的连通图的最优路径问题。

通过本实验，我们将学习如何使用最小生成树算法找到一棵连接图的所有节点且总权重最小的树。

2. 实验原理最小生成树是一个连通图的一种生成树，它的所有边的权重之和最小。

最小生成树的求解算法有多种，其中两种常用的算法是 Prim 算法和 Kruskal 算法。

2.1 Prim 算法Prim 算法是一种贪心算法，从一个节点开始，逐步扩展最小生成树的边。

具体步骤如下： 1. 选择一个起始节点作为最小生成树的根节点。

2. 在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

3. 将该节点标记为已访问。

4. 重复步骤 2 和步骤 3，直到所有节点都被访问。

2.2 Kruskal 算法Kruskal 算法也是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。

具体步骤如下： 1. 对所有边按照权重进行排序。

2. 依次选择权重最小的边，如果该边的两个端点不在同一个连通分量中，则将该边加入最小生成树，并将这两个端点合并到同一个连通分量中。

3. 重复步骤 2，直到所有节点都在同一个连通分量中，即最小生成树构建完成。

3. 实验步骤本实验将使用 Prim 算法和 Kruskal 算法分别求解给定图的最小生成树。

3.1 数据准备首先，我们需要准备一个具有权重的连通图作为实验数据。

假设该图有 n 个节点和 m 条边，我们可以使用邻接矩阵或邻接表来表示这个图。

3.2 Prim 算法求解最小生成树1.首先，选择一个起始节点作为最小生成树的根节点，并将该节点标记为已访问。

2.初始化一个空的最小生成树，用于存储最终的结果。

3.重复以下步骤，直到所有节点都被访问：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)一、引言《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。

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

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

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

武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：09计科2班学生姓名：蒋家权，陈相财，吴继伟，梁丽春指导教师：林丽惠完成日期：2011-1-19课程设计项目研究报告目录一、问题分析和任务定义....................................................................................... - 1 -二、实现本程序需要解决的问题如下................................................................... - 1 -三、测试数据........................................................................................................... - 2 -四、算法思想........................................................................................................... - 3 -五、模块划分........................................................................................................... - 4 -六、算法设计与分析............................................................................................... - 7 -七、源程序............................................................................................................. - 11 -八、测试数据......................................................................................................... - 14 -九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 -十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。

实验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户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。

数据结构实验报告-最小生成树（精选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算法求解带权无向连通图的最小生成树。

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

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

本次实验使用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;”即可。

实验五最小生成树一、需求分析1、本程序的目的是要建设一个最经济的网，，输出相应的最小生成树。

在这里都用整型数来代替。

2、测试数据见下程序。

二、概要设计主程序：int main(){初始化；while (条件){接受命令;处理命令;}return 0;}三、详细设计#include<iostream>//头文件using namespace std;#define MAX_VERTEX_NUM 20//最大结点数#define MAX 200typedef struct Close//结构体{char adjvex;int lowcost;}Close,close[MAX_VERTEX_NUM];typedef struct ArcNode{int adjvex;ArcNode *nextarc;int info;}ArcNode;typedef struct VNode{char data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList verties;int vexnum,arcnum;}ALGraph;ALGraph G;//对象Gint LocateVek(ALGraph ,char );//返回结点位置int minimum(close);//返回最小数void MinSpanTree_PRIM(ALGraph,char);//最小生成树void Create(ALGraph &);//创建邻接表int main(){char a;int i=1;Create(G);/*for(int i=1;i<=G.vexnum;i++){for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)cout<<G.verties[i].data<<"---"<<G.verties[s->adjvex].data<<"===="<<s->info<<endl; }*/while(i){cout<<"输入起点 : ";cin>>a;MinSpanTree_PRIM(G,a);cout<<"如果结束输入'0',否则输入'1':";cin>>i;}return 0;}int LocateVek(ALGraph G,char u){int i;for(i=1;i<=G.vexnum;i++)if(u==G.verties[i].data)return i;return -1;}int minimum(close m)//返回最小数{int i=0,j,n=200;for(i=1;i<=G.vexnum;i++)if(m[i].lowcost<n&&m[i].lowcost!=0){n=m[i].lowcost;j=i;}return j;}void MinSpanTree_PRIM(ALGraph G,char u){int j,k,a;close closedge;ArcNode *s,*p,*q;for(j=1;j<=MAX_VERTEX_NUM;j++)closedge[j].lowcost=MAX;//把所有值都赋为最大k=LocateVek(G,u);for(j=1;j<=G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc)if(j==s->adjvex){closedge[j].lowcost=s->info;break;}}closedge[k].lowcost=0;cout<<"最小生成树 : "<<"{";//查找并输出最小生成树for(j=1;j<G.vexnum;j++){k=minimum(closedge);cout<<"("<<closedge[k].adjvex<<","<<G.verties[k].data<<")";closedge[k].lowcost=0;for(int i=1;i<=G.vexnum;i++){for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc)if(p->info<closedge[i].lowcost&&i==p->adjvex){closedge[i].adjvex=G.verties[k].data;closedge[i].lowcost=p->info;}}}cout<<"}"<<endl;cout<<"边及对应权值: "<<endl;//输出边及对应权值for(j=G.vexnum;j>=1;j--){if(closedge[j].lowcost==0&&G.verties[j].data!=u){ cout<<"("<<closedge[j].adjvex<<","<<G.verties[j].data<<") ==";a=closedge[j].adjvex;for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc)if(a-64==q->adjvex)cout<<q->info<<endl;}}}void Create(ALGraph &G){int i,j,k,x;char a,b;ArcNode *s;cout<<"输入顶点数(1-20):";cin>>G.vexnum;cout<<"输入边数:";cin>>G.arcnum;cout<<"输入顶点信息:"<<endl;for(i=1;i<=G.vexnum;i++){cin>>G.verties[i].data;G.verties[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cout<<"输入相邻两结点和权值 ";cin>>a>>b;cin>>x;j=a-64;k=b-64;//将字符型转化成整数型s=new ArcNode;s->info=x;s->adjvex=k;s->nextarc=G.verties[j].firstarc;G.verties[j].firstarc=s;s=new ArcNode;s->info=x;s->adjvex=j;s->nextarc=G.verties[k].firstarc;G.verties[k].firstarc=s;}}四、调试分析1、在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。

数据结构实验最小生成树数据结构实验报告最小生成树问题一、问题描述:若要在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;}五(调试分析:将选边的过程输出来检验算法的正确性。

最小生成树实验报告1.引言最小生成树（Minimum Spanning Tree，简称MST）是图论中的重要概念，在各个领域都有广泛的应用。

最小生成树是指在给定的加权连通图中，选择一个子集，使得该子集包含了所有的顶点，并且所有边的权值之和最小。

本实验主要目的是探讨最小生成树的算法并比较它们的效率和准确性。

2.实验方法本次实验使用Python编程语言实现了两种著名的最小生成树算法：Prim算法和Kruskal算法。

Prim算法是一种贪心算法，从一个顶点开始不断扩张集合，直到包含所有顶点，生成最小生成树。

Kruskal算法则是基于并查集的算法，将边按照权值排序后逐一加入生成树，同时要保证加入的边不会产生环路。

3.实验过程首先，我们从文件中读取了一张加权无向图的数据。

图的表示采用邻接矩阵的方式，即用一个二维数组来存储顶点之间的连接关系和权值。

读取完图的数据后，我们分别使用Prim算法和Kruskal算法求解最小生成树。

在Prim算法中，我们使用一个辅助数组来记录顶点是否已被访问过，然后从任意一个顶点开始，依次将与当前集合相邻的顶点加入，并选择权值最小的边。

直到所有顶点都被访问过，并形成了一个最小生成树。

在Kruskal算法中，我们首先将所有边按照权值从小到大进行排序。

然后，从权值最小的边开始，逐一将边加入生成树。

加入时，需要判断两个顶点是否在同一个连通分量中，以避免产生环路。

实验中，我们使用了Python中的heapq库来实现了堆排序，以加快Prim算法的运行速度。

4.实验结果经过实验，我们得到了图的最小生成树以及对应的权值。

实验数据显示，当图中顶点较少时，Prim算法和Kruskal算法几乎没有明显的差别。

但当图的规模增大时，Prim算法明显比Kruskal算法更快。

5.实验分析从实验结果可以看出，Prim算法和Kruskal算法都可以求解最小生成树，但在不同情况下它们的性能表现并不相同。

Prim算法适用于稠密图，因为它的时间复杂度与顶点的平方成正比；而Kruskal算法适用于稀疏图，因为它的时间复杂度与边的数量成正比。

#include<stdio.h>#include<stdlib.h>#define MAXLEAF 100#define INF 100000#define EDGENUMBER MAXLEAF*MAXLEAF/2typedef int EdgeType;typedef int VertexType;typedef struct{EdgeType val[MAXLEAF][MAXLEAF];VertexType ves[MAXLEAF];int v;int e;}MGraph;typedef struct{int vex1,vex2;int w;}kedge;void creat_MGraph(MGraph *M){int i,j,k;int w;printf("请输入图的顶点个数及边数：\n");scanf("%d%d",&(M->v),&(M->e));printf("请依次填充顶点信息：\n");for(i=0;i<M->v;i++)scanf("%d",&(M->ves[i]));for(i=0;i<M->v;i++)for(j=0;j<M->v;j++)if(i==j) M->val[i][j]=0;else M->val[i][j]=INF;printf("请依次输入图的边两个顶点顶点的权值：(格式：a b c)\n");for(k=0;k<M->e;k++){scanf("%d%d%d",&i,&j,&w);M->val[i-1][j-1]=w;M->val[j-1][i-1]=w;}}VertexType kruskal(MGraph M){int tag[MAXLEAF];kedge Ke[EDGENUMBER];int i,j;VertexType length=0;int n=0;for(i=0;i<M.v;i++) tag[i]=i;for(i=0;i<M.v;i++)for(j=i+1;j<M.v;j++)if(M.val[i][j]!=INF){Ke[n].vex1=i;Ke[n].vex2=j;Ke[n++].w=M.val[i][j];}kedge temp;for(i=0;i<n-1;i++)for(j=0;j<n-i-1;j++)if(Ke[j].w>Ke[j+1].w){temp=Ke[j+1];Ke[j+1]=Ke[j];Ke[j]=temp;}for(i=0;i<n;i++){int first,second;first = tag[Ke[i].vex1];second = tag[Ke[i].vex2];if(first!=second){length+=Ke[i].w;printf("%d->%d: %d\n",Ke[i].vex1,Ke[i].vex2,Ke[i].w);tag[Ke[i].vex2]=first;for(j=0;j<M.v;j++){if(second==tag[j])tag[j]=first;}}}return length;}int main(){MGraph M;int len;creat_MGraph(&M);printf("最小生成树：\n");len=kruskal(M);printf("最小成本：%d",len);return 0;}。

【关键字】报告最小生成树算法➢问题描述设G=(V,E)是一个无向连通带权图，E中每条边(v,w)的权为c(v,w)。

如果G的一个子图G`是一棵包含G的所有顶点的书，则称G`为G的生成树。

生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树就称为G的最小生成树。

给定一个无向连通带权图，构造一个最小生成树。

➢设计思想利用Prim算法求最小生成树，Prim算法是利用贪心策略设计的算法。

设G=(V,E)是一个连通带权图，V={1，2，…，n}。

构造G的一棵最小生成树的Prim算法的基本思想是：首先置U={1},然后，只要U是V的真子集，就做如下的贪心选择：选取满足条件i∈U,j∈V-U,且使c(i,j)达到最小的边(i,j),并将顶点j添加到U中。

这个过程一致进行到U=V时为止。

在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

➢时间复杂度Prim算法的Pascal语言描述如下：Procedure PRIM(c:array[1..n,1..n] of real);Varlowcost:array[1..n] of real;closest:array[1..n] of integer;i,j,k,min,integer;begin(1)for i:=2 to n do(2)begin{初始化，此时U只含有顶点1}(3)lowcost[i]:=c[1,i];(4)Closest[i]:=1;(5)end;(6)for i:=2 to n do(7)begin {寻找顶点分别在V-U与U中边权最小的边}(8)min:=lowcost[i];(9)j:=i;(10)For k:=2 to n do(11)If lowcost[k]<min then(12)Begin(13)Min:=lowcost[k];(14)j:=k;(15)End;(16)print(j,closest[j]);{输出找到的边}(17)Lowcost[j]:=∞;{将j添加到U}(18)For k:=2 to n do {调整lowcost和closest}(19)if(c[j,k]<lowcost[k])and(lowcost[k]< ∞)then(20)Begin(21)Lowcost[k]:=c[j,k];(22)Closest[k]:=j;(23)End(24)End(25)End;{PRIM}上述过程中第(6)~(24)行的for循环要执行n-1次，每次执行时，第(10)~(15)行和第(18)~(23)行的for循环都要O(n)时间，所以Prim算法所需的计算时间为O(n)。

最小生成树实验报告最小生成树（Minimum Spanning Tree，MST）是图论中的一个重要概念，用于在一个连通带权无向图中找到一个子图，使得这个子图是一个树（即无环连通图），并且所有边的权值之和最小。

最小生成树在诸多领域有着广泛的应用，如网络设计、电力传输等。

在本次实验中，我们实现了最小生成树算法，并将其运用到多个实际问题上。

下面将依次介绍算法原理、实现过程、实验结果以及对实验的进一步改进。

1.算法原理Kruskal算法的基本思想是，首先将所有边按照权值从小到大排序，然后从最小的边开始，逐一加入生成树，直到生成树包含了所有的顶点。

在加入一条边时，需要判断这条边将两个顶点连通起来是否会形成环，如果不会则加入生成树。

Prim算法的基本思想是，从一个顶点开始，逐步加入生成树的顶点，每次加入一个顶点时，选择一个离生成树最近的点，并将这个点加入生成树。

通过不断的选择顶点和加入边，最终得到最小生成树。

2.实现过程首先，我们实现了图的数据结构和边的数据结构。

在图的数据结构中，我们定义了图的顶点数和边数，并用邻接矩阵来表示图的连接情况。

边的数据结构包含了两个顶点和边的权值。

其次，我们实现了两种算法。

对于Kruskal算法，我们首先将所有边按照权值从小到大进行排序。

然后，逐个加入边，判断是否形成环。

如果不会形成环，则将该边加入生成树。

最后，我们使用并查集数据结构来判断两个顶点是否连通。

对于Prim算法，我们首先选择一个起点作为生成树的初始顶点，并将其加入生成树。

然后，每次选择一个离生成树最近的顶点，并将其加入生成树，同时更新其他顶点到生成树的距离。

最后，所有顶点都被加入生成树后，得到最小生成树。

3.实验结果我们在实验中选择了不同大小的图进行测试。

经过对比，我们发现Kruskal算法和Prim算法得到的最小生成树结果是一致的，但是Kruskal 算法的时间复杂度要稍高于Prim算法。

具体的结果如下：对于一个边数为10的图，我们得到了如下最小生成树：1-2-4-5-3总权重为12对于一个边数为20的图，我们得到了如下最小生成树：2-1-4-5-3总权重为16对于一个边数为30的图2-1-4-5-6-7-3总权重为22从实验结果来看，无论是规模较小的图还是规模较大的图，我们都能够得到最小生成树，并且所得到的结果是正确的。

最小生成树prim算法实验报告最小生成树Prim算法实验报告引言：最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个重要概念，意为在一个连通图中找到一棵生成树，使得树上所有边的权值之和最小。

Prim算法是一种常用的解决MST问题的贪心算法。

本实验旨在通过实际操作和观察，深入理解Prim算法的原理与过程。

实验目的：1. 理解Prim算法的基本原理；2. 掌握Prim算法的具体实现过程；3. 利用Prim算法求解最小生成树问题；4. 分析Prim算法的时间复杂度。

实验过程：1. 实验环境搭建：在实验开始前，我们需要搭建合适的实验环境。

首先，我们选择一种编程语言，如Python或C++，来实现Prim算法。

其次，我们需要准备一个图的数据集，可以是随机生成的或者是从现实问题中提取的。

最后，我们需要一个用于可视化的工具，以便观察Prim算法的执行过程和结果。

2. Prim算法实现：Prim算法的核心思想是从一个顶点开始，逐步扩展生成树，直到包含所有顶点为止。

具体实现过程如下：a. 初始化一个空的生成树，选择一个起始顶点；b. 在剩余的顶点中，选择与生成树距离最近的顶点，并将其加入生成树；c. 更新生成树与剩余顶点的距离，如果存在更短的路径，则更新；d. 重复步骤b和c，直到生成树包含所有顶点。

3. Prim算法求解最小生成树问题：利用Prim算法求解最小生成树问题的步骤如下：a. 根据实验环境搭建中准备的图数据集，构建图的邻接矩阵或邻接表表示；b. 选择一个起始顶点，将其加入生成树；c. 重复以下步骤，直到生成树包含所有顶点：i. 从生成树中选择一个顶点v，找到与v相连的顶点中距离最小的顶点u； ii. 将顶点u加入生成树，并将(u, v)边加入生成树的边集；iii. 更新生成树与剩余顶点的距离，如果存在更短的路径，则更新。

实验结果与分析：我们通过实验环境搭建和Prim算法实现，成功求解了多个最小生成树问题。

HUNAN UNIVERSITY 课程实习报告
题目：最小生成树
学生姓名：
学生学号：
专业班级：
指导老师：
完成日期：
一、需求分析
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。

如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题
二、概要设计
抽象数据类型
用数组将边的距离及权值进行存储并排序。

算法的基本思想
构造生成树的网一定是无向网。

并设顶点数不超过30个，边权值为小于100的整数。

根据克鲁斯卡尔算法的特点，为便于选择选择权值小的边，存储结构不选用邻接矩阵和邻接表，而是可以用存储边（带权）的数组表示图。

程序的流程
程序由三个模块构成：
（1）从文件中读入图的信息。

（2）利用克鲁斯卡尔算法求网的最小生成树。

（3）以文本形式生成树中各条边以及他们的权值。

三、
四、详细设计
算法的具体步骤
先将用户的输入的顶点和边的数量，根据这些信息构建出图的结构，最后对边的权值进行排序。

输入和输出的格式
输入：
输入顶点和边的个数及顶点之间的权值。

输出：
输出最小生成树的序列。

五、测试结果
六、实验心得
实验的时候不是这个结果啊，可能是哪个环节出了错误，但是思想没有问题的，通过本次实验学会了用C++实现最小生成树。

友情提示：范文可能无法思考和涵盖全面，供参考!最好找专业人士起草或审核后使用，感谢您的下载！。

实验报告课程名：数据结构(C语言版) 实验名：最小生成树姓名：班级：学号：时间：2014.11.26一实验目的与要求1. 掌握生成最小生成树的算法2. 利用C 语言实现Prim 算法或者Kruskal 算法二实验内容•将一个图存储起来•求取该图的最小生成树三实验结果与分析程序：#include <stdio.h>#include <stdlib.h>#define MAX 100#define MAXCOST 0x7fffffffint graph[MAX][MAX];int Prim(int graph[][MAX], int n){/* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */int lowcost[MAX];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */int mst[MAX];int i, j, min, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化 */for (i = 2; i <= n; i++){/* 最短距离初始化为其他节点到1号节点的距离 */lowcost[i] = graph[1][i];/* 标记所有节点的起点皆为默认的1号节点 */mst[i] = 1;}/* 标记1号节点加入生成树 */mst[1] = 0;/* n个节点至少需要n-1条边构成最小生成树 */for (i = 2; i <= n; i++){min = MAXCOST;minid = 0;/* 找满足条件的最小权值边的节点minid */for (j = 2; j <= n; j++){/* 边权值较小且不在生成树中 */if (lowcost[j] < min && lowcost[j] != 0){min = lowcost[j];minid = j;}}/* 输出生成树边的信息:起点，终点，权值 */printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);/* 累加权值 */sum += min;/* 标记节点minid加入生成树 */lowcost[minid] = 0;/* 更新当前节点minid到其他节点的权值 */for (j = 2; j <= n; j++){/* 发现更小的权值 */if (graph[minid][j] < lowcost[j]){/* 更新权值信息 */lowcost[j] = graph[minid][j];/* 更新最小权值边的起点 */mst[j] = minid;}}}/* 返回最小权值和 */return sum;}int main(){int i, j, k, m, n;int x, y, cost;char chx, chy;/* 读取节点和边的数目 */scanf("%d%d", &m, &n);getchar();/* 初始化图，所有节点间距离为无穷大 */for (i = 1; i <= m; i++){for (j = 1; j <= m; j++){graph[i][j] = MAXCOST;}}/* 读取边信息 */for (k = 0; k < n; k++){scanf("%c %c %d", &chx, &chy, &cost);getchar();i = chx - 'A' + 1;j = chy - 'A' + 1;graph[i][j] = cost;graph[j][i] = cost;}/* 求解最小生成树 */cost = Prim(graph, m);/* 输出最小权值和 */printf("Total:%d\n", cost);//system("pause");return 0;}运行结果：图1.最小生成树运行结果。

北京理工大学软件学院一、实验目的1. 通过上机程序，进一步加深对最小生成树的理解。

2. 掌握Kruskal算法。

3. 学会用程序解决离散数学中的问题。

4. 增强我们编写程序的能力。

二、实验内容求带权无向联通平面图的最小生成树三、实验环境我的实验依旧是在VC6.0实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。

四、实验原理和实现过程利用Kruskal算法求最小生成树，原理如下：1.选取最小权边e1，置边数j←1.2.i=n-1结束，否则转c。

3.设已经选择的边为e1,e2,……，ei,在G中选取不同于e1,e2,……ei的边，使｛e1,e2,……，ei,ei+1｝中无回路且ei+1是满足此条件的最小边。

4.i←i+1，转b。

根据这个，还有以下思路：由G生成的最小生成树T所包含的边的集合1．按非降序权重将E中的边排序2．建立n个单元素集（每个顶点一个）3．最小生成树的边集合T初始为空4 .while |T|<n-15.令e(x,y)为E中的下一条边6. if包含x的集合不是与包含y的集合不是同一个集合then7.将e(x,y)加入到T8.将包含x的集合和包含y的集合合并9.end if10.end while五、实验源代码及分析#include<stdio.h>struct Edge{int from, to, weight; //定义一个数据结构，存放点和边的关系以及边的权值};Edge edge[100], temp; //用定义的数据结构来定义一个数组和一个变量int i, j, n, m;int p[100];int seek(int x) //用来找出当前端点所在集合编号{if(p[x]==x)return x;elsereturn p[x]=seek(p[x]);}Int Kruskal(){int x, y,k=0;for(i=0;i<100;i++)p[i]=i;for(i=0;i<m;i++){x=seek(edge[k].from); //找出当前边两个端点所在集合编号y=seek(edge[k].to);if(x!=y) //如果在不同集合，合并{printf("(%d, %d): %d\n",edge[k].from, edge[k].to, edge[k].weight); //输出这时的边的端点和权值p[x]=y;}k++;}return 0;}int main(){printf("Please input the number of the nodes and edges:\n");scanf("%d%d",&n,&m); //输入有n个节点m条边printf("Please input the edges and its weight:\n");for(i=0;i<m;i++){scanf("%d%d%d",&edge[i].from, &edge[i].to, &edge[i].weight); //输入每一条边的起点、终点和权值}for(i=0;i<m-1;i++) //对边的权值进行从小到大的排列for(j=i+1;j<m;j++)if(edge[i].weight>edge[j].weight){temp=edge[i];edge[i]=edge[j];edge[j]=temp;}printf("The minimum spanning tree is:\n");Kruskal(); //调用Kruskal算法return 0;其中运用seek函数找出当前端点所在集合编号。