费用为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的边。如果连接两个之前不连接的分量,则添加边。如果这个图最初是连通的,算法则是可行的。
参考资料:
洛谷P3623
费用为k的生成树
https://lijianxiong.work/2021/20210718/