最小生成树
2026-03-08
简介
在一个图中,找出边权和最小的一棵树使其联通所有点,称为最小生成树。
次小生成树
次小生成树分为两种,一种是非严格次小生成树,也就是边权不小于最小生成树的至少有一个边不同的树;另一种为严格次小生成树,即边权严格大于最小生成树的一棵树。
朴素求法
假设一个无向图有最小生成树和严格次小生成树。
则我们可以选择一条不在最小生成树中的边,将其插进最小生成树里,一定会构成一个环,这个时候需要删除这个环上的次大值,就能构成一个严格次小生成树,然后对所有边的严格次小生成树取最小值即可。
时间复杂度 O(n2)。复杂度瓶颈为预处理边权最大和次大值。
最近公共祖先优化
这里使用倍增 LCA,即有一个 fi,j 表示 i 向上跳 2j 步的节点。
这个时候,我们需要的边一定是两个点路径上的所有最大值和次大值中选出来的。
也就是说,我们可以预处理节点 i 向上跳 2j 步中所有边的最大值和次大值。
时间复杂度 O(nlogn)。
