徐州工程学院数据结构最小生成树实验文档

徐州工程学院数据结构最小生成树实验文档一、实验目的1.理解最小生成树的概念和意义。2.掌握求解最小生成树的基本算法，如Prim算法和Kruskal算法。3.通过编程实现上述算法，提高对数据结构和算法的运用能力，培养解决实际问题的编程思维。4.分析和比较不同算法的时间复杂度和空间复杂度，加深对算法性能的理解。

二、实验环境1.编程语言：[具体编程语言，如C、C++或Java]2.开发工具：[相应的集成开发环境，如VisualStudio、Eclipse等]

三、实验内容

（一）问题描述给定一个无向连通图G=(V,E)，其中V是顶点集合，E是边集合。每条边(u,v)∈E都有一个权值w(u,v)。最小生成树（MinimumSpanningTree,MST）是图G的一个子图，它包含图G的所有顶点，并且边的权值之和最小。

（二）算法设计

1.Prim算法基本思想：从图中任意一个顶点开始，将其加入到生成树的顶点集合中。然后每次从与生成树顶点集合相邻的边中选择权值最小的边，将其对应的顶点加入到生成树顶点集合中，直到所有顶点都被加入为止。数据结构：使用邻接矩阵`graph[MAXV][MAXV]`来存储图的边权值，其中`graph[i][j]`表示顶点i和顶点j之间的边权值，如果不存在边则设为一个较大的值（如INF）。使用数组`lowcost[MAXV]`来记录每个顶点到生成树顶点集合的最小边权值。使用数组`closest[MAXV]`来记录每个顶点到生成树顶点集合的最小边所连接的生成树顶点。算法步骤：1.初始化：选择一个起始顶点v0，将`lowcost[v0]=0`，其他顶点的`lowcost`值设为`graph[v0][i]`（i为其他顶点），`closest`值设为v0。2.循环n1次（n为顶点数）：找到`lowcost`值最小且未加入生成树的顶点vmin。将vmin加入生成树，输出边`(closest[vmin],vmin)`。更新与vmin相邻的顶点的`lowcost`值和`closest`值：如果`graph[vmin][i]<lowcost[i]`，则`lowcost[i]=graph[vmin][i]`，`closest[i]=vmin`。

2.Kruskal算法基本思想：将图的所有边按照权值从小到大排序，然后依次选择权值最小的边，如果该边加入后不会形成环，则将其加入到生成树中，直到生成树包含所有顶点。数据结构：使用结构体数组`edge[MAXE]`来存储图的所有边，其中包含边的两个顶点和权值。使用并查集（UnionFind）数据结构来判断加入边后是否会形成环。算法步骤：1.将所有边按照权值从小到大排序。2.初始化并查集。3.依次选择权值最小的边：如果该边的两个顶点属于不同的集合，则将该边加入生成树，并合并这两个顶点所在的集合。如果该边的两个顶点属于同一个集合，则跳过该边，继续选择下一条边。

（三）代码实现

1.Prim算法代码示例（以C语言为例）```cinclude<stdio.h>include<limits.h>

defineMAXV100defineINFINT_MAX

intgraph[MAXV][MAXV];intlowcost[MAXV];intclosest[MAXV];

voidprim(intn,intv0){inti,j,min;for(i=0;i<n;i++){lowcost[i]=graph[v0][i];closest[i]=v0;}for(i=1;i<n;i++){min=INF;intvmin=1;for(j=0;j<n;j++){if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];vmin=j;}}if(vmin!=1){printf("(%d,%d)%d\n",closest[vmin],vmin,lowcost[vmin]);lowcost[vmin]=0;for(j=0;j<n;j++){if(graph[vmin][j]<lowcost[j]){lowcost[j]=graph[vmin][j];closest[j]=vmin;}}}}}```

2.Kruskal算法代码示例（以C语言为例）```cinclude<stdio.h>include<stdlib.h>

defineMAXE100

typedefstruct{intu,v,w;}Edge;

Edgeedge[MAXE];

intparent[MAXV];

intfind(intx){if(parent[x]==1)returnx;returnparent[x]=find(parent[x]);}

voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx!=rooty)parent[rooty]=rootx;}

intpare(constvoid*a,constvoid*b){Edge*edgeA=(Edge*)a;Edge*edgeB=(Edge*)b;returnedgeA>wedgeB>w;}

voidkruskal(intn,inte){inti,j;for(i=0;i<n;i++)parent[i]=1;qsort(edge,e,sizeof(Edge),pare);for(i=0;i<e;i++){intu=edge[i].u;intv=edge[i].v;introotu=find(u);introotv=find(v);if(rootu!=rootv){printf("(%d,%d)%d\n",u,v,edge[i].w);unionSet(u,v);}}}```

四、实验步骤

（一）输入图的信息1.编写输入函数，提示用户输入图的顶点数n和边数e。2.依次输入每条边的两个顶点和权值，存储在邻接矩阵或边数组中。

（二）选择并运行算法1.在主函数中提供菜单选项，让用户选择运行Prim算法或Kruskal算法。2.根据用户选择调用相应的算法函数，并输出最小生成树的边及其权值。

（三）测试与调试1.使用不同的测试用例对程序进行测试，包括简单的图和复杂的图。2.检查程序是否能够正确输出最小生成树的结果，对于错误的输入是否有适当的提示。3.调试程序，解决可能出现的编译错误、运行时错误和逻辑错误。

五、实验结果与分析

（一）测试用例1图的信息：顶点数n=4边数e=5边及权值：(0,1)10,(0,2)6,(0,3)5,(1,3)15,(2,3)4Prim算法结果：(0,3)5(2,3)4(0,2)6(0,1)10Kruskal算法结果：(2,3)4(0,3)5(0,2)6(0,1)10

（二）测试用例2图的信息：顶点数n=5边数e=7边及权值：(0,1)1,(0,2)5,(0,3)3,(1,2)6,(1,4)4,(2,3)4,(3,4)2Prim算法结果：(0,1)1(0,3)3(3,4)2(1,4)4(0,2)5Kruskal算法结果：(0,1)1(3,4)2(0,3)3(1,4)4(0,2)5

（三）算法性能分析1.时间复杂度：Prim算法：邻接矩阵存储时，时间复杂度为O(n^2)；邻接表存储时，时间复杂度为O((n+e)logn)。Kruskal算法：时间复杂度为O(eloge)，其中e为边数。如果使用并查集的路径压缩优化，时间复杂度接近O(eloge)。2.空间复杂度：Prim算法：邻接矩阵存储时，空间复杂度为O(n^2)；邻接表存储时，空间复杂度为O(n+e)。Kruskal算法：空间复杂度为O(e)，用于存储边数组，以及O(n)用于并查集。

（四）结果讨论1.从测试结果可以看出，Prim算法和Kruskal算法都能正确求出最小生成树。2.在时间复杂度方面，对于边数较少而顶点数较多的图，Prim算法（邻接矩阵）可能效率较低，此时Kruskal算法更优；对于边数较多的图，两者的性能差异可能较小。3.在空间复杂度方面，Prim算法的邻接矩阵存储方式占用空间较大，而Kruskal算法相对较小。

六、实验总结通过本次实验，成功实现了Prim算法和Kruskal算法来求解最小生成树。对这两种算法的基本思想、数据结构和实现步骤有了更深入的理解。通过实际编程和测试，分析了它们的时间复杂度和空间复杂度，并比较了在不同情况下的性能表现。

在实验过程中，遇到了一些问题，如输入格式的处理、边界条件的判断以及算法逻辑的正确性。通过仔细调试和分析，逐步解决了这些问题，提高了编程能力和对算法的掌握程度。

本次实验不仅加深了对最小生成树概念和算法的理解，