www.jbmf.net > 生成树的构造方法只有一种

生成树的构造方法只有一种

如果图中所有边的权值都不同,只有一种最小生成树 但是如果有2条或以上的边有相同权值,这个最小生成树就不一定唯一了 不过即使不唯一,这个最小的权值和一定唯一的

普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w.在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小.之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止.克鲁斯卡尔算法克鲁斯卡尔算法的基本思想:为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小.具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止.

构造最小生成树的方法:最初生成树为空,即没有一个结点和一条边,首先选择一个顶点作为生成树的根,然后每次从不在生成树中的边中选择一条权值尽可能小的边,为了保证加入到生成树中的边不会造成回路,与该边邻接的两个顶点必须一个已经在生成树中,一个则不在生成树中,若网中有n个顶点(这里考虑的网是一个连通无向图),则按这种条件选择n-1边就可以得到这个网的最小生成树了

a 最小生成树,这也是最小生成树的一个性质,构造最小生成树的方法都需要以此为基准其他各个答案没有必然性

最小生成树有两个算法:这里介绍一种,还有一种叫prim,可自行百度1. 对所有边按长度排序,创建n(点数)个集合,S1={N1},S2={N2},..,Sn={Nn};2. 从小到大枚举所有边,若边的起点和终点在一个集合内,则跳过.否则合并两个集合,并把这条边放入最小生成树.3. 若生成树内已有n条边,停止遍历,否则返回2.

对于一颗图G,如果其子图G'满足V'=V,且G'是一棵树,那么G'就是图G的一颗生成树.生成树是一棵树,按照树的定义,每个顶点都能访问到任何一个其它顶点.

c

正确,因为权可能相等.举一个极端的例子,当权值都相等的时候,就相当于是无权的图.

设该图5个顶点从左到右从上到下为 V1 V2 V3 V4 V5从任一点开始生成生成树,要使其不为环,则必须断开V1-V2 V1-V3 V1-V4其中两个或V2-V5 V3-V5 V4-V5其中两个边.所以一共是 5个顶点 * (左3个边中任意两个的组合+右两边中任意两个的组合)= 5 * (C3:2 + C3:2) = 30

网站地图

All rights reserved Powered by www.jbmf.net

copyright ©right 2010-2021。
www.jbmf.net内容来自网络,如有侵犯请联系客服。zhit325@qq.com