数据结构最小生成树讨论课报告.doc

数据结构最小生成树讨论课报告.doc:..《数据结构》讨论课报告课程名称: 最小生成树的求解方法及分析指导老师:班级:计算机科学与技术四班目录1•摘要 2•讨论课目的和任务3•讨论课内容 •-・ 1・摘要给定一个连通网络,要求构造具有最小代价的生成树时,也即使生成树的各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权,那么具有最小权值的生成树就构成了连通网络的最小生成树。构造最小生成树的算法有很多种,其中大多数的算法都利用了最小生成树的一个性质,简称为MST性质:假设G二(V,E)是一个连通网络,U是V中的一个真子集,若存在顶点ueu和顶点ve(v_U)的边(u,v)是一条具有最小权值的边,则必存在G的一棵最小生成树包括这条边(u,v)。利用该性质构造最小生成树的常用算法主要有:Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法。关键词:最小生成树,Prim算法,Kruskal算法2•讨论课目的和任务已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路,其中网的顶点表示城市,边表示两个城市之间的线路,赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树,每一棵生成树都可以是一个通信网。我们要选择一棵生成树,使总的耗费最小。,英存储方式可以采用邻接矩阵形式,需要定义两个数组,一个存储顶点,一个存储边,存储边的数组表明节点间的连通关系和边的权值。利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。按顺序输出生成树中各条边以及权值。={V,E}中的某一顶点U0出发,选择与它关联的具有最小权值的边(UO,v),将其顶点加入到生成树的顶点集合U中。以后每一步,一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网中的所有顶点都加入到生成树顶点集合U中为止。・2图形解析4・(一棵树),则它是一个含有n棵树的一个森林。从网的边集E中选取一条权值最小的边,若该条边的两个顶点分屈不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有--棵树,也即子图中含有n-l条边为止。・(Boruvka)算法Sollin(Brouvka)其实是前面介绍两种算法的综合,每次迭代同时扩展多课子树,直到得到最小生成树T。(一开始是单个定点)的最近邻居。(类似Prim算法)(类似Kruskal算法)如果这条边连成的两个顶点同属于一个集合,则不处理,否则检测这条边连接的两个子树,如果是连接这两个子树的最小边,则更新(合并)由于每次循环迭代时,每棵树都会合并成一棵较大的子树,因此每次循环迭代都会使子树的数量至少减少一半,或者说第i次迭代每个分量大小至少为。所以,循环迭代的总次数为0(logn)o每次循坏迭代所需要的计算时间:对于第2步,每次检查所有边0(m),去更新每个连通分量的最小弧;对于第3步,合并个子树。所以总的复杂度为0(E*logV)。89101112131415161718192021222324252627282930TEdgenn[maxE],a[maxE];voidBoruvka([])算法如下:typedefstruct{intv;intw;doubLewt;}Edge;2typederstruct{intV;intE;doubLe**adj}Graph;3/*nn存储每个分量的最邻近,a存储尚未删除且还没在MST中4的边h用于访问要检查的下一条边N用于存放下一步所保存的边5每一步都对应着检查剩余的边,连接不同分量的顶点的边被保6留在下一步中最后每一步将每个分量与它最邻近的分量合并,7并将最近邻边添加到MST中inth,i,j,k,v,w,N;Edgee;intE=GRAPHedges(a,G);for(UFinit(G->V);E!=0;E=N){for(k=0;k<G->V;k++)nn[k]=Edge(G->VJG->V,maxWT);for(h=0,N=0;h<E;h++){i=find(a[h].v);j=find(a[