最小生成树和最短路径数据结构实验

最小生成树（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.在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

求最小生成树(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. 首先将所有的边按照权重从小到大排序，并分别初始化每个顶点的连通分量编号。

实验报告六（数学学院08级4班080204015 余燕川）实验目的:通过对图的基本知识的学习, 掌握图的基本概念, 构造最小生成树, 在此基础上上机实践, 调试程序。

实验题目:对一个给定的图G（V, E）, 构造最小生成树。

三、实验分析:1.假设网G（V, E）是连通的, 从顶点u出发构造G的最小生成树T, 开始时, 记T=（U, B）, 其中U是T顶点集合, B是T的边集合；2、开始时U={u0 }( u0 ∈V)B=空,重复执行下述操作:在所有的u ∈U,V∈V-U组成的边(u,v)中找出一条权值最小的边（u0,v0）并入边集B中,同时将v0加入顶点集U,直到U=V为止, 此时T中必中必有n-1条边, 则T=（U, B）为G的最小生成树。

四、实验部骤:（1）构写程序的大体框架；（2）具体编写每个操作的程序；（3）程序的检查；（4）程序的调试；五、程序调试问题:输入顶点后, 边的信息输不进去；如下图：六、实验结果:输入顶点数为5, 边数为8, 顶点为v1,v2,v3,v4,v5;后面出现了问题。

七、实验程序:#define MAXSIZE 100#define max 10typedef char datatype;typedef struct{datatype vexs[MAXSIZE];int edges[MAXSIZE][MAXSIZE];int n,e;}graph;struct{char end;int len;}minedge[max];void Creatgraph(graph *ga){int i,j,k,w;printf("Please put the number of graph's vexs and edges:");scanf("%d,%d",&(ga->n),&(ga->e));printf("shu rui ding dian:\n");for(i=0;i<ga->n;i++)scanf("%2c\n",&(ga->vexs[i]));for(i=0;i<ga->n;i++)for(j=0;j<ga->n;j++)ga->edges[i][j]=100;for(k=0;k<ga->e;k++){printf("shu rui %d tiao bian de xu hao i,j and quan zhi w:",k+1);scanf("%d,%d,%d\n",&i,&j,&w);ga->edges[i][j]=w;ga->edges[j][i]=w;}}void prim(graph *g,char u){int v,k,j=0,min;for (v=1;v<=g->n;v++)if(v!=u){minedge[v].end=u;minedge[v].len=g->edges[v][u];}minedge[u].len=0;for(k=1;k<g->n;j++){min=minedge[k].len;v=j;}if(min==MAXSIZE){printf("error!");}printf("zui xiao sheng cheng shu:");printf("%d %d",v,minedge[v].end);minedge[v].len=-minedge[v].len; for(j=1;j<=g->n;j++)if(g->edges[j][v]<minedge[j].len) {minedge[j].len=g->edges[j][v]; minedge[j].end=v;}}void main(){int i,j;graph *g;g=(graph *)malloc(sizeof(graph)); Creatgraph(g);printf("Sheng cheng shu:\n"); prim(g,g->vexs[0]);}。

3、单源最短路径给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。

另外，还给定 V 中的一个顶点，称为源。

现在我们要计算从源到所有其他各顶点的最短路径长度。

这里的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。

既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

具体步骤是：1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。

②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。

2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。

3、调整T中各顶点到源点v的最短路径。

因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。

调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。

4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

实验代码如下：#include <iostream>using namespace std;#define max 10000void yuan(int n,int **a,int m){int *b=new int[n+1],*s=new int[n+1];int i,j;for(i=1;i<=n;i++){b[i]=a[m][i];s[i]=0;}s[m]=1;for(int ii=1;ii<n;ii++){int min=max,w=1;for(int k=1;k<=n;k++)if(min>b[k]&&(!s[k])){w=k;min=b[k];}s[w]=1;for(i=1;i<=n;i++)if(!s[i]){if(b[i]>b[w]+a[w][i])b[i]=b[w]+a[w][i];}}for(j=1;j<=n;j++)if(j!=m)cout<<m<<"-->"<<j<<" : "<<b[j]<<endl;}int main(){int n,m,**a,i,j;while(cin>>n>>m){a=new int*[n+1];for(i=0;i<=n;i++)a[i]=new int[n+1]; for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];yuan(n,a,m);}return 0; }从得到的结果上分析，固定点的位置是从2开始遍历的，2到1的最短路径是32,2到3的最短路径是44,2到4的最短路径是92；当然，也可以从1或3或4开始遍历。

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

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

姓名:XXX
实验名称: 图的最小生成树和最短路径
实验项目 : 图的最小生成树和最短路径
实验日期 :2012.11.16
实验类型: 设计型
实验目的:
理解图的最小生成树的概念
掌握图的最小生成树的构造方法（尤其是prim算法）
掌握图的单源点的最短路径的求解方法（尤其是狄杰斯特拉算法）
程序功能:（以下题目任选一个完成）
（1）某个网络工程需要在下图中的各个地点之间铺设通讯网络，使得每个地点之间是相通的，为节约成本，要求铺设的总的线路长度最短。

请编程为上述问题设计一个方案。

（2）编程实现求下图中从四中出发到其余各地点的最短路径。

程序代码：
运行结果：
总结。

数据结构实验报告-最小生成树（精选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++语言集成开发环境。

图的最短路径与最小生成树算法实践在计算机科学中，图（Graph）是一种抽象的数据结构，它由节点（Vertex）和边（Edge）组成。

图的最短路径和最小生成树是图算法中的两个重要问题，它们在网络、交通、社交网络等领域有着广泛的应用。

本文将介绍图的最短路径算法和最小生成树算法的实践。

一、图的最短路径算法实践图的最短路径算法用于求解两个节点之间的最短路径，常用的算法有迪杰斯特拉算法（Dijkstra Algorithm）和弗洛伊德算法（Floyd Algorithm）。

（这里可以介绍迪杰斯特拉算法和弗洛伊德算法的思想和流程，注意使用文字和图示来说明）在实际应用中，最短路径算法可以被用于许多场景，比如导航系统中的路径规划、物流配送中的最优路线选择等。

例如，在一座城市中，我们需要规划出从A地到B地的最短路径，可以使用最短路径算法来求解。

二、图的最小生成树算法实践图的最小生成树算法用于找到一个连通图的最小生成树，最常用的算法是普里姆算法（Prim Algorithm）和克鲁斯卡尔算法（Kruskal Algorithm）。

（这里可以介绍普里姆算法和克鲁斯卡尔算法的思想和流程，注意使用文字和图示来说明）最小生成树算法在实际应用中也有很多用途，比如电力系统的最优输电线路规划、通信网络的构建等。

例如，在一个城市的交通网络中，我们希望为每个区域之间建立电缆线路，以便实现高速、稳定的通信，可以使用最小生成树算法来求解。

三、图的最短路径和最小生成树算法在实践中的应用图的最短路径和最小生成树算法在现代社会中有广泛的应用，下面将介绍一些实际应用场景。

1. 路径规划最短路径算法可以用于导航系统中的路径规划。

通过输入起点和终点，最短路径算法可以帮助我们找到从起点到终点的最短路径，以便在导航系统上为驾驶员提供准确的路线指引。

2. 物流配送在物流配送中，最短路径算法可以用于选择最优路线，以节省时间和成本。

通过计算各个配送点之间的距离和路径，可以帮助物流公司规划出最佳配送路线，提高配送效率。

数据结构的应用的最小生成树算法与最短路径算法数据结构的应用：最小生成树算法与最短路径算法在计算机科学中，数据结构是指组织和存储数据的方式。

数据结构广泛应用于算法设计和问题解决中，其中最小生成树算法和最短路径算法是两个关键的应用之一。

本文将就这两个算法进行详细介绍与分析。

一、最小生成树算法最小生成树算法用于解决无向图中选择一棵具有最小权重的生成树的问题。

生成树是指一个无向图的子图，它包含图中的所有顶点，但是只包含足以构成一棵树的n-1条边。

最小生成树算法的目标是找到权重之和最小的生成树。

1. Kruskal算法Kruskal算法是一种常用的最小生成树算法。

它的基本思想是按照边的权重递增顺序选择边，并且如果加入该边会形成回路，则不加入该边。

算法步骤：（1）将所有边按照权重从小到大进行排序。

（2）初始化一个空集合，用于存放生成树的边。

（3）遍历排序后的边，如果加入该边不会形成回路，则将该边加入生成树集合。

（4）重复步骤3直到生成树包含n-1条边。

Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。

该算法常用于解决网络设计、电路布线等问题。

2. Prim算法Prim算法也是一种常用的最小生成树算法。

与Kruskal算法不同的是，Prim算法以顶点为基础，每次选择与当前生成树距离最近的顶点加入生成树。

算法步骤：（1）选择任意一个顶点作为起始点，并将该顶点加入生成树。

（2）对于生成树之外的顶点，计算其与生成树上顶点的边的权重，并找到其中权重最小的边对应的顶点。

（3）将权重最小的边添加到生成树，并将对应的顶点加入生成树。

（4）重复步骤2和步骤3直到生成树包含n-1条边。

Prim算法的时间复杂度为O(n^2)，其中n为顶点的数量。

该算法常用于解决通信网络、电力网络等问题。

二、最短路径算法最短路径算法用于解决在图中找到两个顶点之间的最短路径的问题。

最短路径可以根据边的权重来定义，也可以根据边的长度、时间等其他因素来定义。

实验报告June 18 2015姓名：陈斌学号：E11314079 专业：13计算机科学与技术数据结构第八次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.06.18 教师签字成绩实验报告【实验名称】最小生成树和最短路径【实验目的】(1)掌握最小生成树以及最短路径的相关概念；(2)掌握Prim算法和Kruskal算法；(3)掌握Dijkstra算法【实验内容】采用普里姆算法求最小生成树(1)编写一个算法，对于教材图7.16(a)所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。

图的存储结构自选。

(2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。

（提示：a.先对边按权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。

b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。

c.重复b步直至输出n-1条边。

）源代码：head.h:#include<string.h>#include<ctype.h>#include<malloc.h> //malloc( )#include<limits.h> // INT ,MAX#include<stdio.h> //EOF,NULL#include<stdlib.h> //atoi( )#include<io.h> //eof( )#include<math.h> //floor( ),ceil( ),abs( )#include<process.h> //exit( )#include<iostream.h> //cout,cin//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1//OVERFLOW 在math.h 中已定义为3typedef int Status;typedef int Boolean; // 布尔类型main.cpp:#include"head.h"typedef int VRType;typedef char InfoType;#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */typedef char VertexType[MAX_NAME];/*图的数组(邻接矩阵)存储表示*/#define INFINITY INT_MAX /* 用整型最大值代替∞*/#define MAX_VERTEX_NUM 20 /* 最大顶点个数*/typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */typedef struct{VRType adj; /* 顶点关系类型。

本科学生设计性实验报告项目组长______ 学号________成员 _____________________________专业一软件工程班级_______实验项目名称__________指导教师及职称 _________开课学期2012至2013年第一学期上课时间2012年12月3日至12月24日1、实验目的:通过实现某复杂算法，使学生理解数据结构基本概念、掌握栈、队列、树、图等的应用等，熟练使用C或者C++巩固同学们在课堂上所学的知识激发同学们主动学习和应用新知识的意识。

本设计性实验由学生在下列题目中任选，或自拟题目：多项式求解；哈夫曼编码；迷宫求解；表达式求值；银行排队系统模拟；最小生成树；拓扑排序；最短路径；关键路径2、实验场地及仪器、设备和材料：实验场地：实验室？仪器设备：联想台式机一台，Microsoft Visual C++ 6.0#in elude <iostream> using n amespace std;class Min iSpa nTree{private:int arcs[100][100];int vexnum;int edge;int lowcost[100];int closest[100]; public:void creatGraph(){int m[100][100];cout<<"请输入顶点数：” cin> >vex num;cout<<"请输入边的数：”cin> >edge;for(i nt i=1;i<=vex nu m;i++) for(i nt j=1;j<=vex nu m;j++) {arcs[i][j]=INT_MAX; m[i][j]=0;}for(i=0;i<edge;i++){int a,b,c;cout<<"请输入顶点1的编号(大于0)：";cin> >a;cout<<"请输入顶点2的编号(大于0):";cin> >b;cout<<"请输入 V"<<a<<",V"<<b<<" 边的权值：” cin> >c;arcs[a][b]=c;arcs[b][a]=c; m[a][b]=m[b][a]=1;}cout<<"该图的邻接矩阵为："<<e ndl;for(i=1;i<=vex nu m;i++)for(i nt j=1;j<=vex nu m;j++){ cout<<m[i][j]<<""; if(j==vex num) cout<<e ndl;}}void prim()//构造最小生成树 {int min;for(i nt i=2;i<=vex nu m;i++)//存储弧的权值 //存储顶点数 //存储边数或弧数 〃存储到某结点最小的权值 //存储对应权值的结点编号 〃 给每条边给最大的整型初值lowcost[i]=arcs[1][i]; //把与1邻接的结点的权值储存在lowcost[i]中closest[i]=1; //并把编号储存在closest[i]中}lowcost[1]=0; 〃从1号结点开始访问cout<<"V"<<1<<"";for(i=2;i<=vex nu m;i++){min=INT_MAX;int k=0;for(i nt j=2;j<=vex nu m;j++)if((lowcost[j]<mi n)&&(l owcost[j]!=0)) //找到最小权值的那个邻接的结点{mi n=lowcost[j];k=j; //把它的编号赋给k ；}cout<<"V"<<k<<" "; //输出最小生成树lowcost[k]=0; //设为0表示已访问for(j=2;j<=vex nu m;j++)if(arcs[k][j]<lowcost[j]) {lowcost[j]=arcs[k][j];closest[j]=k;}} cout<<e ndl;}};int mai n(){Min iSpa nTree a;a.creatGraph();cout<<"该图的最小生成树为：";a.prim();return 0; //如果它到某结点的权值更小〃就把它的权值重新写入lowcost[j]中〃并修改结点的编号、实验结果与分析1、实验目的、场地及仪器、设备和材料、实验思路等见实验设计方案2、实验现象、数据及结果输入：3、对实验现象、数据及观察结果的分析与讨论:实验现象正确，符合最小生成树的要求。

摘要最小生成树是数据结构中图的一种重要应用，在图中对于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算法求解最小生成树。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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