最小生成树与次小生成树
作者:
解矣
,
2023-11-09 14:16:55
,
所有人可见
,
阅读 110
最小生成树与次小生成树的性质
在一个图中,边权最小的的那条边一定在最小生成树中。
若将图中的一些节点划分到一个集合中,所有节点划分到若干个集合。将一个集合当成一个块,如果在这些块之间做最小生成树,那么这些块之间的边权最小的边一定在最小生成树中。相当于将这个集合缩成了一个点。
最小生成树与次小生成树之间的关系
最小生成树与(严格或非严格)次小生成树一定可以只相差一条边。也就是说将最小生成树中的某一条边删掉,然后添加另一条边,一定可以得到次小生成树。对于严格次小生成树,一定只能相差一条长度不一样的边,不能相差两条。因为如果相差两条不一样的边,一定可以将其中一条换成原来的最小生成树中的边。
次小生成树的构造方法
1. 先构造最小生成树。遍历该最小生成树中的所有边,将这一条边删去,然后重新构造最小生成树。对所有边进行这样操作后,得到的权值最小的生成树即为次小生成树。
2. 先构造最小生成树。然后枚举所有的非最小生成树中的边,将该边添加到最小生成树中。此时这条边的两个点之间会形成环。删去该环中权值最大/次大的边,得到新的生成树。对所有边这样操作后,得到权值最小的即为次小生成树。需要注意的是,对于严格次小生成树,添加的边的权值一定要大于删除的权值,也就是说如果环中权值最大的边如果等于添加的边,需要删除环中次大的边。