网站排名突然没有了,平邑的网站都是谁做的,da面板安装wordpress,池州专业网站建设怎么样数据结构之生成树及最小生成树 1、生成树概念2、最小生成树 数据结构是程序设计的重要基础#xff0c;它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发#xff0c;分析和研究计算机加工的数据的特性#xff0c;以便为应用所… 数据结构之生成树及最小生成树 1、生成树概念2、最小生成树 数据结构是程序设计的重要基础它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发分析和研究计算机加工的数据的特性以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法为提高利用计算机解决问题的效率服务。 数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的
逻辑结构数据元素及元素之间关系的存储称为
存储结构(或物理结构)。数据结构按照逻辑关系的不同分为
线性结构和
非线性结构两大类其中非线性结构又可分为树结构和图结构。 树结构是一种非常重要的非线性结构该结构中的一个数据元素可以有两个或两个以上的直接后继元素树可以用来描述客观世界中广泛存在的层次结构关系。 1、生成树概念 对于有n个顶点的连通图至少有n-1条边而生成树中恰好有n-1条边所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边则必然形成回路。下图(a)所示的无向图的一个生成树如下图(b所示下图(c不是生成树因为存在回路。 图的生成树不是唯一的。从不同的顶点出发选择不同的存储方式用不同的求解方法可以得到不同的生成树。对于非连通图而言每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树把它们称为非连通图的生成树森林。按深度和广度优先搜索进行遍历将得到不同的生成树分别称为深度优先生成树和广度优先生成树。例如下图所示的是上图(a的一棵深度优先生成树和一棵广度优先生成树。
2、最小生成树 对于连通网来说边是带权值的生成树的各边也带权值因此把生成树各边的权值总和称为生成树的权把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。 常用的最小生成树求解算法有普里姆Prim算法和克鲁斯卡尔Kruskal算法。 1普里姆Prim算法。 假设N(V,E是连通网TE是N上最小生成树中边的集合。算法从顶点集合U{u0}(u0∈V)、边的集合TE{开始重复执行下述操作在所有u∈U, v∈V-U的边u,v)∈E中找一条代价最小的边u0,v0)把这条边并入集合TE同时将v0并入集合U直到UV时为止。此时TE中必有n-1条边T(V,{TE}为N的最小生成树。 由此可知普里姆算法构造最小生成树的过程是以一个顶点集合U{u0}作为初态不断寻找与U中顶点相邻且代价最小的边的另一个顶点扩充U集合直到UV时为止。 用普里姆算法构造最小生成树的过程如下图所示。 普里姆算法的时间复杂度为0(n2)与图中的边数无关因此该算法适合于求边稠密的网的最小生成树。 2克鲁斯卡尔(Kruskal)算法。 克鲁斯卡尔求最小生成树的算法思想为假设连通网N(V,E)令最小生成树的初始状态为只有 n 个项点而无边的非连通图 TV{}图中每个顶点自成一个连通分量。在E选择代价最小的边若该边依附的项点落在T中不同的连通分量上则将此边加入到T中否则舍去此边而选择下一条代价最小的边。依此类推直到T中所有顶点都在同一连通分量上为止。 用克鲁斯卡尔算法构造上图(a)所示网的最小生成树的过程如下图所示。 克售斯卡尔算法的时间复杂度为 O(e㏒e)与图中的顶点数无关因此该算法适合于求边稀疏的网的最小生成树。
