数据结构实验报告-最小生成树（精选6篇）
篇1：数据结构实验报告-最小生成树
电 子 科 技 大 学
实
验
报
告
学生姓名：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
struct {
int
vex;
int
gno;}TVex,*TpVex;
typedef
struct {
int
vhead, vtail;
int
wght;
int
flag;}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;i
if(G->EdgeList[i].wght
minwght=G->EdgeList[i].wght;
j=i;
} }
return j;}
void create(TpGraph G){
int i,j,minEdge;
for(i=0;i
minEdge=findmin(G);
if(G->VexList[G->EdgeList[minEdge].vhead].gno== G->VexList[G->EdgeList[minEdge].vtail].gno)
G->EdgeList[minEdge].flag=-1;
else{
G->EdgeList[minEdge].flag=1;
G->VexList[G->EdgeList[minEdge].vtail].gno= G->VexList[G->EdgeList[minEdge].vhead].gno;
for(j=0;j
if
(G->VexList[j].gno==G->VexList[G->EdgeList[minEdge].vtail].gno)
G->VexList[j].gno=G->VexList[G->EdgeList[minEdge].vhead].gno;
}
printf(“head:%d tail:%d
weight:%dn”,G->EdgeList[minEdge].vhead,G->EdgeList[minEdge].vtail,G->EdgeList[minEdge].wght);
i++;
}
}
} void read_file(char *filename,char *message,TpGraph
G){ int a = 0,b,c,i,j,vexlist[20]={0},m,k=0;FILE *pfile=NULL;pfile=fopen(filename,“r”);if(!pfile){
printf(“Open file failn”);
exit(0);} else
printf(“Open file success!n”);
G->EdgeList=(TpEdge)malloc(sizeof(TpEdge)*21);G->VexList=(TpVex)malloc(sizeof(TpVex)*7);for(i = 0;i < 20;++i){
fscanf(pfile , “%dt%dt%dn” , &a, &b, &c);
G->EdgeList[i].vhead=a;
G->EdgeList[i].vtail=b;
G->EdgeList[i].wght=c;
printf(“%dt%dt%dn”, a, b, c);
vexlist[k]=a;
k++;
for(m=0;m if(vexlist[m]==vexlist[k-1]) k--; } vexlist[k]=b; k++; for(m=0;m if(vexlist[m]==vexlist[k-1]) k--; } } for(j=0;j<6;j++) G->VexList[j].vex=j+1; G->nedge=20;G->nvex=j;} int main(){ char *filename=“/Users/pro/Desktop/实验/数据结构实验3/graph.txt”; TGraph G; int Edges[20][3] = {0}; read_file(filename,Edges,&G); begin(&G); create(&G); return 0;} 九、程序运行结果： 运行程序： 实验成功。 十、实验结论： 克鲁斯卡尔算法是一种能够体现“贪心”的精髓的贪心算法，它所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。 十一、总结及心得体会： 克鲁斯卡尔算法的时间复杂度为O（eloge），因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。 设计题目：最小生成树 专业：xxxxxx 院系：计算机学院 姓名：xxxxxxxxx 学号：xxxxxx 时间：2013年10月7日 数据结构课程设计报告 最小生成树 目 录 一、设计目的……………………………………………………………….-2- 二、算法思想分析………………………………………………………-2-1.算法思想………………………………………………………………..-3-1）普里姆（Prim）算法思想……………………………………………………….-3-2）克鲁斯卡尔（Kruskal）算法思想..........................................-3-2.系统采用的数据结构和算法………………………………-3- 三、算法的描述与实现……………………………………………….-4- 四、用户手册………………………………………………………………-7- 五、总结…………………………………………………………………….-10- 六、参考文献…………………………………………………………….-10- 七、附录（源代码）………………………………………………...-10- 数据结构课程设计报告 最小生成树 1.算法思想 1)普里姆（Prim）算法思想 a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列； b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列； c)重复b)直到所有的节点出列。2)克鲁斯卡尔（Kruskal）算法思想 为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。 具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。 由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。 2.系统采用的数据结构和算法 1)数据结构 Typedef int Vertextype;Typedef int adimatrix[MaxVertexNum][MaxVertexNum];Typedef int Vertextype vexlist[MaxVertexNum];Typedef int VexType; 数据结构课程设计报告 最小生成树 1.Great_adjmatrix()和Great_adjmatrix2()是两种建立图的方法； 2.克鲁斯卡尔算法（Kruskal）： Void kruskal(GraphMatrix * pgraph,Edge mst[]){int i,j,min,vx,vy;int weight,minweight;Edge edge;for(i=0;i n-1;i++){mst[i].start_vex = 0;Mst[i].stop_vex = i+1;Mst[i].weight = pgraph->arcs[0][i+1];} for(i=0;i n-1;i++)//共n-1条边 {minweight = MAX;min = i;for(j=i;j n-1;j++)//从所有（vx,vy）（vx∈U,vy∈V-U）中选出最短的边 if(mst[j].weight for(j=i+1;j n-1;j++) 数据结构课程设计报告 最小生成树 j=MST[k-1].endvex;//定位于权值最小边的尾顶点 for(i=k;i 4.out_edgeset()功能为显示最小生成树。 四、用户手册 1.运行程序，得到如下窗口： 2.输入顶点数，选择算法： 1）当输入的顶点数小于10时，选择Kruskal算法，如下图 数据结构课程设计报告 最小生成树 五、总结 该程序实现了在n个城市之间建设网络，既保证了连通性，也成为了最经济的架设方法。程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。不过，该程序仍有不足之处，图的输入数据过大，易出错，不易返回，仍需完善。 六、参考文献 [1]《数据结构程序设计题典》 李春葆编 清华大学出版社 [2]《数据结构（C语言版）》 严蔚敏 吴伟民编 清华大学出版社 [3]《数据结构课程设计》 苏仕华编 机械工业出版社 七、附录：（源代码） #include 数据结构课程设计报告 最小生成树 { scanf(“%d%d%d”,&i,&j,&w);GA[i][j]=GA[j][i]=w;//对称 } } void Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph){ int i,j,k,w,x,y; printf(“输入%d个顶点序号(0-m-1)，序号从0开始。”,m);for(i=0;i GA[i][j]=MaxValue;printf(“请输入有多少条边。n”);scanf(“%d”,&e);printf(“输入%d条无向带权边（序号 序号 权值）：n”,e);for(k=0;k 数据结构课程设计报告 最小生成树 /* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */ edge = mst[min];mst[min] = mst[i];mst[i] = edge;vx = mst[i].stop_vex;/* vx为刚加入最小生成树的顶点的下标 */ for(j = i+1;j < pgraph->n-1;j++){ /* 调整mst[i+1]到mst[n-1] */ vy=mst[j].stop_vex;weight = pgraph->arcs[vx][vy];if(weight < mst[j].weight){ mst[j].weight = weight;mst[j].start_vex = vx;} } } } void out_edgeset(edgeset MST,int e)//显示最小生成树 { int k;printf(“最小的消耗路线为n”);for(k=0;k printf(“(%d %d %d)n”,MST[k].fromvex,MST[k].endvex,MST[k].weight);} void prim(adjmatrix GA,edgeset MST,int n)//利用prim算法从0点出发求图的最小生成树 数据结构课程设计报告 最小生成树 int a;system(“color 71”);//改变屏幕颜色 printf(“ ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“ ┃㊣ 必做题：最小生成树 ㊣┃n”);printf(“ ┃ 姓名：xxxx ┃n”);printf(“ ┃ 学号：xxxxxxxxx ┃n”);printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);vexlist GV;//顶点表 adjmatrix GA;//边表 edgeset MST;//最小生成树 do{ printf(“输入图的顶点数n，我们将根据您输入的数据大小选择合适的算法。n”);scanf(“%d”,&n);if(n>=10)//大于10用prim算法来实现，否则kruskal算法来实现 { printf(“用prim算法从0点出发求图的最小生成树为：n”);printf(“请输入图的边数。n”);canf(“%d”,&e);Creat_adjmatrix(GV, GA, n, e);//创建图 prim(GA,MST,n);//生成最小生成树 迄今为止,许多学者对赋权无向图中的最小生成树问题已经进行了研究,提出了很多有效地求解算法,例如破圈法、避圈法等。其实最小生成树问题也可以用整数规划来表示,谢金星教授已给出了最小生成树问题的数学表达式[1],但其中的无圈等价条件没有证明,并且无圈的等价条件还有许多种表示方法[2,3,4,5,6,7,8,9],这些表示方法虽然数学表达式不同,但本质上是相同的。因此,该文将对无圈的等价条件给出证明,并给出赋权有向图中最小生成树问题的数学模型。 2 赋权无向图中最小生成树问题的数学模型 对一赋权无向图G,我们假定G无重边和环,即G为简单图,事实上,若G不是简单图,则有以下引理保证也可以求G的最小生成树。 引理:给定赋权无向图G,若G有重边和环,则去掉后结果不会比原来的差。 证明:若G有环,直接去掉,若G有重边,则将重边按权从大到小排列,只留下边权最小的边,其余的重边全去掉,得到新图G*。由于最小生成树问题是要求权最小的生成树,故由G*的生成方式知,G*的最小生成树就是G的最小生成树。 我们用有向图的思想来解决无向图的最小生成树问题。事实上,我们把无向图中的边加倍,看成是不同方向的双弧,这样,就把无向图转化成了有向图。我们首先给出有向树及其相关概念。 定义1如果有向图在不考虑边的方向时,是一棵树,那么这个有向图称为有向树。进一步,如果有一颗有向树T,恰有一个顶点的入度为0,其余顶点的入度都为1,则称T为根树。 定义2在有向树T=(V,A)中,当(u,v)∈A时,称u是v的父亲,v是u的儿子。 给定赋权无向图我们将它变成有向图,用dij表示两顶点vi与vj之间的距离,即边的权值;用决策变量xij表示顶点vi与vj之间的父子关系,xij=1表示顶点vi是vj的父辈,xij=0表示vi不是vj的父亲。在赋权无向图的最小生成树中,我们可以指定任一个分枝点为树的根,故不妨设顶点v1为生成树的根。则该问题的数学模型为: 其中第一组约束表示根v1至少有一条边连接到其它的顶点;第二组约束表示除根外,每个顶点只能有一条边进入;同时注意到,各条边均不构成圈.目标函数表示总距离最小。 对于数学模型(1.1)中的“各边不构成圈”的条件,从模型应用和实现的角度,我们给出各边不构成圈的充要条件: 3 赋权有向图最小生成树问题的数学模型 设T(V,A)是一棵根树,vk(k=1,2,…,n)为树根,则有以下定理: 定理3当G(V,A)为赋权有向图时,G的最小生成树问题的数学模型为: 其中第一组约束表示根vk至少有一条边连接到其它的顶点;第二组约束表示除根外,每个顶点只能有一条边进入;同时注意到,各条边均不构成圈.目标函数表示总距离最小.模型(1.4)可以利用lingo、matlab数学软件等求解。 4 实例验证 例:考虑具有8个顶点v1,v2,…,v8的赋权无向图,定义在边上的权重如表1所示,求该图的最小生成树。 注:“——”表示两点之间无边相连。2 解:由定理,该问题的数学模型为: 5 结论 本文对于赋权无向图的最小生成树问题,分析了数学模型,给出了其中无圈的证明,并推广到赋权有向图中,从而使得借助于lingo程序可以方便地求解最小生成树问题。同时,我们还发现,将目标函数换成max,就可以求图G的权和最大的生成树。赋权无向图最小生成树模型的建立,有助于研究其他图论问题,如旅行商问题,最短路问题等。 摘要：对图论中赋权无向图中最小生成树问题的数学模型,分析了建立的过程,并证明了各边不构成圈的一个等价条件,最后推广到有向图中,为用数学软件求解图论问题打下基础。 关键词：最小生成树；唯一；prim算法；kruskal算法；次小生成树 中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011)06-0000-02 Minimum Spanning Tree If the Unique Wu Yuliang,Kong Fanlong (Central China Normal University,Wuhan430079,China) Abstract:Minimum spanning tree is a classic problem of graph theory,find the minimum spanning tree minimum spanning tree,and find the weight and get enough attention,and few people to study the minimum spanning tree is unique.For a given graph is concerned,because the weights and the minimum spanning tree is determined,so the minimum spanning tree is not unique and only if the shape of the minimum spanning tree is not unique.Determine whether the proposed minimum spanning tree,and the only three ways to give their analysis and evaluation. Keywords:Minimum spanning tree;Unique;Prim algorithm;Kruskal algorithm;Small spanning tree 一、三种方法判断最小生成树(MST)是否唯一 （一）借助prim算法提出的方法 prim算法的基本思想是：首先选取图中的任意一个顶点v作为树的根加入生成树的集合Q中，之后不断往生成树中(集合Q中)添加顶点w，顶点w满足与集合Q中的某个顶点之间有边，且该边上的权值是此时所有连接集合Q中的结点与不在集合Q中的结点的边中权值最小的，如此加入n-1个结点后，就形成了ＭＳＴ。 按照上面的思想，可以知道最小生成树加入点的顺序。最小生成树是由点和边组成的，点在上边已经确定，我们还需确定边才能最终确定最小生成树。每次加入顶点w时(第一点除外)，顶点w都满足与集合Q中的某个顶点有当时最小权的边，把集合Q中的那个顶点看作顶点w的前驱结点。那么到算法结束时，我们都能得到每个点(第一个点除外)的前驱结点，将每个点(第一个点除外)与它的前驱结点相连，就有n-1条边了，最小生成树构造完成。 该算法的伪代码描述： PrimMST(G，r)//求图G的以r为根的MST，通过求每个点的前驱结点来求MST {//初始化，Q←{r}，除r外的所有前驱结点都为r且与Q的最短距离都是与r的距离。 InitCandidateSet(…); for(k=0;k { for(v=0;v (u，v)=SelectLishtEdge(…);//选取最小的边，其中u为已加入集合Q的点，v为没有加入集合Q中的点 Q←Q∪{v};//将点v加入集合Q中 pre[v]=u;//同时记录v的前驱结点 ModifyCandidateSet(…);//根据加入的v调整不在Q中的点与在Q中的最短距离 } } 在上述算法中，每次把集合Q外的最靠近集合Q中的点加入集合Q，所以只有当集合Q外存在多个与集合Q中的点具有相同的最小边权值时，MST才有可能不唯一。当出现这种情况时，加入下一个点时枚举所有的这些点，最后判断每次得到的形状是否一样。这样固然可以，但时间复杂度太高了，这里提出如下方法。 当有可能存在MST不唯一时，考虑两个极端的MST。一个是每次遇到多种选择时，都选择序号最小的点加入集合Q，另一个是每次遇到多种选择时，加入序号最大的点。如果这两个极端的MST完全一样，那么MST就是唯一的。这种方法的时空复杂度与prim算法的时空复杂度一样。所以时间复杂度为O(n^2)，空间复杂度为O(n^2)。 （二）借助kruskal算法提出的方法 kruskal算法的基本思想是：为使生成树上总的权值之和达到最小，应使每一条边上的权值尽可能小，自然应从权值最小的边选起，直至选出n-1条权值最小的边为止，然而这n-1条边必须不构成回路。所以每次加入最小的边之前判断是否会构成回路，不构成回路就加入该边，构成回路就丢弃该边。 按照以上思想，具体可以这样操作：用邻接表的数据结构存储每条边的信息，然后将每个点都看作一个单独的集合，从小到大枚举每条边，如果边的两端点不在同一个集合的话，就加入这条边，并且将这两个点所属的集合合并，否则，就不加这条边(因为同一个集合的点一定是可达的，然后加入该条边的话就一定会构成回路)。算法结束后就有n-1条不会产生回路的边了，MST的形状也就出来了。 Kruskal每一步都是加入最小权的边，所以当且仅当要加入的侯选边中存在两条最小权值且连接的是两个相同集合的边时(此时这两条边不能同时加入，取舍导致了最终结果的不唯一)，MST才不唯一。所以在加入每条边时，都要判断后面是否存在与它权值相等且连接的是两相同集合的边。 该算法的伪代码描述为： KruskalMST(G)//图的边存储在e中，MST的边全部存在E中 { InitCandidateSet(…);//初始化，一条边都没取，且每个顶点都有各自的集合 Sort(e);//按边的权值从小到大排序 for(k=1;k<=m;k++)//m为边的条数。从小到大枚举每条边 { if(Set(e[k].u)!=Set(e[k].v))//如果两端点在同一个集合中，一定会产生回路。 { for(j=k+1;;j++)//找后面与它权值相等且连接相同集合的边 { if(e[j].w==e[k].w) { if(边j和边k连接的是两个相同的集合) 输出MST不唯一，return; } else break;//如果发现连接的不是相同的集合立即退出循环 } Union(e[k].u，e[k].v);//将两端点所在集合合并为一个集合 E[num++]=k;//记录k为MST中的边 } } 输出MST唯一;//若没发现MST不唯一的情况，则MST唯一。 } （三）借助次小生成树提出的方法 次小生成树是所有生成树中权值和第二小的生成树。判断最小生成树是否唯一可以转化到判断次小生成树的权值和是否与最小生成树的权值和相等的问题上来。如果权值和相等，那么最小生成树不唯一，否则唯一。 求次小生成树的基本思想是：先求最小生成树，然后枚举最小生成树的每一条边(总共有n-1条)，删去后再求最小生成树，这样得到的所有生成树中最小的就是次小生成树。 该算法的伪代码描述为： SST(G) { sum1=KruskalMST(G);//最小生成树的权值和 for(sum2=maxint，i=0;i { j=KruskalMST(G-E[i]);//去掉MST中的第i条边后再求最小生成树 if(j } if(sum1==sum2) MST不唯一 else MST唯一 } 二、分析评价三种方法 首先从时空复杂度分析这三种方法：第一种方法只是用prim算法求了两次MST，所以跟prim算法的时空复杂度是一样的，都是O(n^2)。在第二种方法中，kruskal的时间复杂度的瓶颈在于对边排序，后面对边扫描是O(e)，而判断MST是否唯一时，排序是一样的，只是扫描时，每次加入一条边时都要向后判断是否存在一条与其权值相等且连接相同两集合的边，所以时间复杂度与边的权值相等的程度相关，最好的时候为O(elog2e)，最坏的时候为O(e^2)，空间复杂度与kruskal算法一样O(e)。第三种方法用了n次kruskal算法求MST，所以时间复杂度为O(nelog2e)，空间复杂度仍是O(e)。然后从思考的难易比较，如果知道次小生成树的话，不得不说第三种方法是最好想的，而第一种（第二种）方法就需要对prim算法（kruskal算法）有深入的理解才能琢磨出。最后总整体来评价这三种算法，第三种算法是比较容易想的，当想不到前面两种方法时，牺牲时间总比没有方法好；而第二种方法在图是稀疏图且相同边权的边不是很多的情况下，时空复杂度是相当可观的；而第一种方法在稠密图且相同边权很多的情况下，优势非常明显。 三、结束语 本文针对最小生成树是否唯一提出了三种解决方法，并且从多种角度分析它们的利弊以及说明它们的适用范围。 参考文献： [1]R.L.Graham & P.Hell.Minimum Spanning Tree.Annals of the History of Computing，Volume 7，Number 1，January 1985.43-57 [2]Thomas H.Cormen.Introduction to algorithm[M].高教出版社,2002 [3]严蔚敏,陈文博.数据结构及应用算法教程[M].清华大学出版社,2001 [4]汪汀.最小生成树问题的拓展[Z].IOI2004国家集训队论文,2004 (青海师范大学数学系，青海 810000) 摘要：本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法)，重点介绍了一种求解最小生成树问题的DNA 算法，进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用。 关键字：最小生成树 Kruskal算法 Prim算法 破圈法 DNA 算法 Several algorithm of solving minimum spanning tree and its application Xiangnan-kong (Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree(Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm), and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree;Kruskal algorithm;Prim algorithm; Broken circle method ;DNA algorithm. 1 引言 最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。 求图的最小生成树有两种常见的算法，一种是Kruskal(克鲁斯卡尔)算法，另一种是Prim(普里姆)算法。这两个算法的基本思想均是基于避圈法，而从相反的角度，破圈法也可构造最小生成树算法。 本文讲述Kruskal算法、Prim算法和破圈法的同时，也着重介绍了一种求解最小生成树问题的DNA 算法。 2 有关最小生成树的理论基础 2.1 有关最小生成树的概念 2.1.1 定义一(图) 一个图G定义为一个偶对(V,E),记作G=(V,E)，其中 (1) (2) V是一个集合，其中的元素称为顶点; E是无序积VDV中的一个子集合，其元素称为边; 2.1.2 定义二(树)：不含圈的连通图称为树。 2.1.3 定义三(生成树)：如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生成树。 2.1.4 定义四(最小树)：设T?是赋权图G的一颗生成树，若对G的任意生成树T都有l T? 2.2 有关最小生成树的定理 2.2.1 定理一(最小树充要条件) 设T是G的一棵生成树，则下列条件都是T为最小树的充要条件 (1) 对任意连枝e′∈GT,有l (e′)=maxe∈CT(e′){(l(e))} (2) 对图G中任意圈C,存在e′∈CT，有l (e′)=maxe∈C{l(e)} (3)对任意树枝e∈T,有l (e)=mine∈ST(e){(l(e′))} (4)对G的任意割集S，在T∩S中存在一条边e，l(e)=mine′∈S 2.2.2 定理二(唯一最小树充要条件) 设T?是G的一棵生成树，则下列条件都是T?是G的唯一最小树的充要条件是下列两个条件中的任一个成立： (1)对任意e∈GT?，e是CT?(e)的唯一权最大的边。 (2)对任意e?∈T?，e?是ST?(e?)的唯一权最小的边。 3 Kruskal(克鲁斯卡尔)算法 3.1 Kruskal算法介绍 Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算法. 第1步 开始把图的边按权的大小由小到大地排列起来，即将图的边排序为a1,a2,…,am,使W a1 ≤W a2 ≤?≤W am 置S=?，i=0,j=1. 第2步 若|S|= i=n?1,则停止。这时G [S]=T即为所求;否则，转向第3步。 第3步 若G [S? aj ]不构成回路，则置e i+1=aj,S=S?{e i+1}, i?i+1,j：=j+1,转向第2步;否则，置j：=j+1，转向第2步。 MST-KRUSKAL(G,w) T(e){l(e′)} 1 A→? 2 for each vertex ?∈V G 3 do Make-Set(v) 4 sort the edge of E into nondecreasing order by weight w 5 for each edge μ,? ∈E,taken in nondecreasing order by weight 6 do if Find-Set(u)≠Find-Set(v) 7 then A←A∪ u,v 8 Union(u,v) 9 retuen A 3.2 Kruskal算法的复杂性 首先在第1步中把边按权的大小由小到大地排列起来，这约需mqlog2m次比较;其次第2步最多循环n次;在第3步中判断G [S? aj ]是否构成回路，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为mqlog2m+n+m+ n(n-1)~O n2log2n 由定理一(1)易见上述算法的正确性。 3.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图2所示 图1 图2 4 Prim(普里姆)算法 4.1 Prim算法介绍 Prim算法的基本思想：首先，选择带权最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。下面我们来介绍这个算法： 设G是n+1个顶点的连通的赋权图。 第1步 取T0为n+1个顶点的空图，T0有n+1个分支(即孤立点)，没有圈。 i，则E(Vi× V i)是一个断第2步 把Ti的n+1-i个分支分成两个子集Vi和V 集。 i)中权最小的边，令T i+1=T i+e i+1,显然，第3步 取e i+1为断集E(Vi× V T i+1没有圈且分支数为 n+1 ? i+1 =n?i. 第4步 当i=n?1时算法停止，Tn中已有n条边，构成G的一棵生成树，当i≠n?1时，令e′= i+1返回第2步。 MST-PRIM(G,w,r) 1 for each u∈V G 2 do key[u] ←∞ 3 π[μ]←NIL 4 key[r] ←0 5 Q ←V G 6 while Q≠? 7 do u ←Extract?Min Q 8 for each v∈Adj u 9 do if v∈Q and w(u,v)< key[v] 10 then π v ←u 11 key[v] ←w(u,v) 4.2 Prim算法的复杂性 下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较，第二次为n-3次比较，第三次是n-4比较，?，因此总的比较为2 n?2 (n? 1)次。在执行第3步时，第一次是n-2次比较，第二次n-3次比较，?，因此总的比较为(n-2)(n-1)次。由此算法的总计算量约为O n2 . 1 4.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图3所示 图3 5 破圈法 5.1 破圈法介绍 该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树，若G 中只有一个回路，则删去G 的回路上的一条边(不删除结点)，则产生的图仍是连通的，且没有回路，则得到的子图就是图G 的一棵生成树，若G 的回路不止一个，只要删去每一个回路上的一条边，直到G 的子图是连通没有回路且与图G 有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样(即删去的边不一样)所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W(T)最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生成树。破圈法的`复杂程度为O n3 . 5.2 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图4所示 成绩：_________ 实验七 二叉树操作验证 一、实验目的 ⑴ 掌握二叉树的逻辑结构； ⑵ 掌握二叉树的二叉链表存储结构； ⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。 二、实验内容 ⑴ 建立一棵含有n个结点的二叉树，采用二叉链表存储； ⑵ 前序（或中序、后序）遍历该二叉树。 三、设计与编码 #include void inorder(void visit(BTreeNode void postorder(void visit(BTreeNode static void fun(BTreeNode data;}//访问结点 protected: BTreeNode //***********************建树******************************* template template //***********************遍历******************************* template {cout <<“递归先序遍历二叉树：”;s.preorder(s.fun);cout < 答：经常忘记对头结点的定义，以至于程序出错，经定义头结点，使程序正常运行。 b)程序运行的结果如何？ 【数据结构实验报告-最小生成树】相关文章： 数据结构实验报告08-25 《数据结构》课程实验报告04-08 数据结构实验报告格式02-21 数据结构实验报告答案02-21 数据结构实验报告一04-13 数据结构实验报告图04-19 数据结构上机实验报告04-24 数据结构实验报告封面05-10 2022《数据结构》上机实验报告 链表04-09 中南大学 数据结构实验报告05-10篇2：数据结构实验报告-最小生成树
篇3：数据结构实验报告-最小生成树
篇4：最小生成树是否唯一
篇5：数据结构实验报告-最小生成树
篇6：数据结构二叉树操作验证实验报告