时间:2021-05-19
次小生成树的定义
设 G=(V,E,w)是连通的无向图,T 是图G 的一个最小生成树。如果有另一棵树T1,满
足不存在树T',ω(T')<ω(T1) ,则称T1是图G的次小生成树。
求解次小生成树的算法
约定:由T 进行一次可行交换得到的新的生成树所组成的集合,称为树T的邻集,记为N(T)。
定理 3:设T是图G的最小生成树,如果T1满足ω(T1)=min{ω(T')| T'∈N(T)},则T1是G
的次小生成树。
证明:如果 T1 不是G 的次小生成树,那么必定存在另一个生成树T',T'=T 使得
ω(T)≤ω(T')<ω(T1),由T1的定义式知T不属于N(T),则
E(T')/E(T)={a1,a2
1,……,at},E(T)/E(T')={b1,b2,……,bt},其中t≥2。根据引理1 知,存在一
个排列bi1,bi2,……,bit,使得T+aj-bij仍然是G 的生成树,且均属于N(T),所以ω(aj)≥ω(bij),
所以ω(T')≥ω(T+aj-bij)≥ω(T1),故矛盾。所以T1是图G 的次小生成树。
通过上述定理,我们就有了解决次小生成树问题的基本思路。
首先先求该图的最小生成树T。时间复杂度O(Vlog2V+E)
然后,求T的邻集中权值和最小的生成树,即图G 的次小生成树。
如果只是简单的枚举,复杂度很高。首先枚举两条边的复杂度是O(VE),再判断该交换是否
可行的复杂度是O(V),则总的时间复杂度是O(V2E)。这样的算法显得很盲目。经过简单的
分析不难发现,每加入一条不在树上的边,总能形成一个环,只有删去环上的一条边,才能
保证交换后仍然是生成树,而删去边的权值越大,新得到的生成树的权值和越小。我们可以
以此将复杂度降为O(VE)。这已经前进了一大步,但仍不够好。
回顾上一个模型——最小度限制生成树,我们也曾面临过类似的问题,并且最终采用动态规
划的方法避免了重复计算,使得复杂度大大降低。对于本题,我们可以采用类似的思想。首
先做一步预处理,求出树上每两个结点之间的路径上的权值最大的边,然后,枚举图中不在
树上的边,有了刚才的预处理,我们就可以用O(1)的时间得到形成的环上的权值最大的边。
如何预处理呢?因为这是一棵树,所以并不需要什么高深的算法,只要简单的BFS 即可。
预处理所要的时间复杂度为O(V2)。
这样,这一步时间复杂度降为O(V2)。
综上所述,次小生成树的时间复杂度为O(V2)。
练习
题目:
题目描述:
最小生成树大家都已经很了解,次小生成树就是图中构成的树的权值和第二小的树,此值也可能等于最小生成树的权值和,你的任务就是设计一个算法计算图的最小生成树。
输入:
存在多组数据,第一行一个正整数t,表示有t组数据。
每组数据第一行有两个整数n和m(2<=n<=100),之后m行,每行三个正整数s,e,w,表示s到e的双向路的权值为w。
输出:
输出次小生成树的值,如果不存在输出-1。
样例输入:
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
样例输出:
4
6
ac代码(注释写的比较清楚):
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法。一、权重图和最小生成树权重图:图的边带权重最小生成树
最小生成树最小生成树(minimumspanningtree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。最小生成树可以用Prim(普里
本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程。1.什么是最小生成树算法?简言之,就是给定一个具有n个顶点的加权的无相连通图,
c++中.dll与.lib文件的生成与使用的详解--------------------------------------------------------
C++遍历二叉树实例详解2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法:(1)前序遍历(2)中序遍历(3)后续遍历以下是经典示例:#in