数据结构课程设计最小生成树的构建实验报告

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

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

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

本次实验我们选择了两种经典的最小生成树算法：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)。

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

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

武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：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算法求解最小生成树。

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

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

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

实验五最小生成树一、需求分析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语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。

数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第 2 学期一、需求分析1.问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

2.基本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。

程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。

3.输入输出以文本形式输出最小生成树，同时输出它们的权值。

通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。

二、概要设计1.设计思路：因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。

根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。

2.数据结构设计：图状结构：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>的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph( &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。

数据结构课程设计目录一. 设计目的.................................................................................................... 错误!未定义书签。

二. 设计内容 (1)三．概要设计 (1)1、功能模块图 (1)2、各个模块详细的功能描述 (2)四．详细设计 (3)1．主函数和其他函数的伪码算法 (3)2、主要函数的程序流程图 (7)3、函数之间的调用关系图 (15)五．测试数据及运行结果 (15)1．正常测试数据及运行结果 (16)2、非正常测试数据及运行结果 (17)六．调试情况，设计技巧及体会 (18)七．参考文献 (19)八．附录：源代码 (19)一. 设计目的课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。

能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。

而且通过数据结构课程设计能够在下述各方面得到锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2、提高程序设计和调试能力。

通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3、培养算法分析能力。

分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

二. 设计内容最小生成树问题:设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

三．概要设计1、功能模块图2、各个模块详细的功能描述※创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。

※功能选择：给用户提示信息，让用户选择相应功能。

※建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。

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

数据结构实验报告名称：最小生成树班级:122姓名：＊*＊＊*学号：*＊**＊＊＊*＊*＊指导老师：***＊**＊*一、设计目的与任务1。

1课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。

1。

2课程设计的任务问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价.对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。

我们要选择一棵生成树，使总的耗费最小。

二、设计方案2。

1需求分析（1）建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表；（2）利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树；（3）输入各城市的数目以及各个城市之间的距离。

将城市之间的距离当做网中各点之间的权值。

按顺序输出生成树中各条边以及它们的权值。

2.2数据结构分析构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根,然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图）,则按这种条件选择n—1边就可以得到这个网的最小生成树了。

详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V—U集合中的元素是不在生成树中的顶点。

首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。

#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;}。

最小生成树实验报告最小生成树（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从实验结果来看，无论是规模较小的图还是规模较大的图，我们都能够得到最小生成树，并且所得到的结果是正确的。

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.最小生成树运行结果。

《数据结构》课程设计报告构造可以使n个城市连接的最小生成树学校：平顶山学院设计题目（问题）描述和要求给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。

二、系统分析与概要设计根据问题描述和要求，系统要求能够显示最小生成树的边，权值和得到的最小生成树的代价。

确定程序的数据结构（抽象数据类型）及“邻接矩阵的数据类型”、“临时数组的存放的数据类型”、邻接矩阵的创建等各模块定义。

做此设计，城市间的道路网用邻接矩阵来表示。

若两个城市之间不存在道路，则将相应的权值设置为自己定义的无穷大值。

此程序的目的是：显示最小生成树的边，权值和得到的最小生成树的代价。

因此该程序的指令是：输入城市数和道路数—>输入城市名—>输入道路信息—>执行prim算法—>输出最小生成树。

三、详细设计和编码1、邻接矩阵的数据类型的定义如下：typedef struct{ int no; /*顶点编号*/string name; /*顶点其他信息*/ } VertexType; /*顶点类型*/typedef struct{ int edges[MAXV][MAXV]; /*邻接矩阵*/int vexnum,arcnum; /*顶点数,弧数*/VertexType vexs[MAXV]; /*存放顶点信息*/ }MGraph;2、临时数组的存放的数据类型struct {int closest; // U集中的顶点序号int lowcost; // 边的权值} closedge[MAXV];int const INF=32767; /*INF表示∞*/3、prime算法实现：（原理见实验说明）void prime(MGraph g,int v){int lowcost[MAXV];int min;int closest[MAXV];int i,j,k;for(i=0;i<g.vexnum;i++){lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.vexnum;i++){min=INF;for(j=0;j<g.vexnum;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("边(%d,%d)权为:%d\n",closest[k],k,min);lowcost[k]=0;for(j=0;j<g.vexnum;j++)if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}4、邻接矩阵的创建void CreatMGraph(MGraph &M){int n,e;cout<<"输入定点数:";cin>>n;M.vexnum=n;cout<<"输入弧数:";cin>>e;M.arcnum=e;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)M.edges[i][j]=0;elseM.edges[i][j]=INF;}}cout<<"输入边的权：（如1 2 3 表示点到点的权时）"<<endl;for(int i=0;i<2*e;i++){int x,y,z;cin>>x>>y>>z;M.edges[x][y]=z;}cout<<"输入点编号，名字："<<endl;for(int i=0;i<n;i++){int No;string str;cin>>No>>str;M.vexs[i].name=str;M.vexs[i].no=No;}}int const MAXV=16。

课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树研究院(系)：专业：班级：学号：姓名：指导教师：完成日期：目录第 1 章概要设计 ....................................................................1.1题目介绍.........................................................................1.2功能要求.........................................................................1.3总体结构.........................................................................第 2 章详细设计 ....................................................................2.1 主函数的流程图 ................................................................. 2.2 权值位置判断流程图 .............................................................2.3创建邻接矩阵流程图 .............................................................2.4 最小生成树流程图................................................................ 第 3 章调试分析 ....................................................................第 4 章使用说明 ....................................................................参考文献 ............................................................................附录(程序清单) .................................................................第 1 章概要设计1.1题目介绍若要在 n 个城市之间建设通讯网络，只需要架设 n-1条路线即可。