费用为k的生成树

问题:输入无向图G和一个整数k。G中有n个顶点。每条边的费用非1 即2。请在图G中寻找一棵费用为k 的生成树。
(此题为数据结构与算法HW5的bouns题第一题)

算法流程:

先建立两棵生成树——一棵最小生成树,记为R;一棵最大生成树,记为B。

接下来:(该过程能将树R变形为树B)

(1)取一条在树B而不是树R中的边e;

(2)将边e加到树R上;

(3)因为R是一棵生成树,必然产生了一个环,环中也必然有些边不在B,去除其中的一条边

重复这三个步骤,直到满足条件。

时间复杂度:

算法的第一部分需要运行最小生成树算法两次,因此运行时间为O(Elog V)。

算法的第二部分最多重复插值算法V−1次。

插值算法的每次迭代都需要:(i)找到一条边,并将其加到R上,最多需要V次时间;(ii)在循环中寻找一条边从R中移除,这最多需要V个时间。因此,运行插值步骤的总时间最多为$O(V^2)$。因此,算法的总运行时间为$O(V^2+ ElogV)$。

快速解决方案:这个算法的缓慢部分在于,当我们将一棵生成树插入到另一棵生成树时,在生成树中寻找环。

下面是一种避免这种情况的方法:•

  • 首先,识别图中只有权值为1的边的连通分量。

  • 其次,用权值为2的边连接上述连通分量。这可以使用并查集来检查红色连接组件之间的连接性,每次迭代一个权值为2的边。如果连接两个之前不连接的分量,则添加边。如果这个图最初是连通的,算法则是可行的。

参考资料:

新加坡国立大学CS4234课程Problem Set 1

洛谷P3623


费用为k的生成树
https://lijianxiong.work/2021/20210718/
作者
LJX
发布于
2021年7月18日
许可协议