如何找到权重不超过 k 的反馈集

Question

任何无向加权图的反馈集都是边的子集，使得在删除 子集中的边，剩下的图是无环的。

给定G = (V, E)，无向带权图，整数k，如何判断是否存在总权重不超过k的反馈集？

谢谢！

Answer 1

最小反馈集永远不会包含断开图中两个分量的边，因此删除反馈集不会改变连通分量，但会使每个连通分量变得非循环。

如果一个无向图是连通且无环的，那么它就是一棵树，所以：

对于图中的每个连通分量，找到最大 权重生成树。您可以通过否定所有权重来使用任何最小权重生成树算法。

不在任何最大权重生成树中的边是最小权重反馈集。

要找到所有最大权重树，我建议在整个图上使用 Kruskal 算法，边按权重降序排序，因为它会一次性找到所有树。然后 select 所有不在任何树中的边。