令 G = (V,E) 为无向图。如果 G 的每个循环在 F 中至少有一条边，则一个边集 F ⊆ E 称为 反馈边集。
(a) 假设 G 未加权。设计一种有效的算法来找到最小尺寸的反馈边集。
(b) 假设 G 是一个带正边权重的加权无向图。设计一个有效的算法来找到一个最小权重的反馈边集。
我的解决方案（需要建议）：
a)最小尺寸反馈边集：由于图是未加权的，我们可以使用 DFS。我们像往常一样从任何顶点开始 DFS。当我们遇到一个后边缘时，我们将它插入到一组反馈边缘中。当 DFS 完成时，集合将是答案。
b)最小权重反馈边集：由于图是加权的，我们可以使用 Kruskal。但克鲁斯卡尔通常从重量最小的边缘开始。如果我们可以否定所有边权重，然后运行 Kruskal，每当我们在同一组件的顶点之间获得一条边时，我们可以将其保存在反馈边集中。最后，否定边缘权重。我建议否定边缘权重的原因是因为我们需要最小的权重反馈集。使用否定权重，Kruskal 将从具有最小权重（实际上是最大）的边开始，并会找到具有较小权重的相同组件的边。
有人可以判断这个解决方案是否正确吗？
是的，您的解决方案是正确的。无向图的最小权重反馈边集是最大权重生成森林的补充。所有生成林具有相同的基数，因此在未加权的情况下，任何生成林（由 DFS 发现）都可以。（证明草图：拟阵。）
反馈弧集确实是 NP 难的，但这是无向的情况。
要在具有正权重的加权有向图中找到最小权重反馈边集：
通过否定权重，观察它相当于找到最大权重反馈边缘集。要找到最大权重反馈边集，请使用 Prim 或 Kruskal 算法构建 MST。然后取那个 MST 的补码。
为什么它有效？这是基于以下观察：
一条边不在任何 MST 中当且仅当存在一个循环，该循环对该循环中的所有其他边具有最大权重。 或者，换句话说，一条边在某个 MST 中当且仅当对于该边所属的每个循环，它在该循环中的所有其他边上不是具有最大权重。
实际上，假设我们有一个具有最大权重的反馈边集，其中存在一个包含该边和另一个权重更大的边的循环，那么用另一个边替换该边将提供一个权重更大的反馈边集。
为了完整起见，观察的证明：
<=) 假设一条边在一个循环中具有最大权重。如果它在某个 MST 中，那么用该循环中的另一个边替换该边将提供一个权重更小的 MST。
=>) 假设对于给定边所属的每个循环，在该循环中都存在一个权重更大的边。如果它不在任何 MST 中，那么将该边添加到 MST 将导致 MST 中的循环。然后从该循环中移除最大权重的边缘（与给定边缘不同）将提供具有较小权重的 MST（并包含该给定边缘）。
这两个问题都是NP完全的。因此，即使是近似有效的（多项式时间）解决方案也不太可能存在（http://en.wikipedia.org/wiki/Feedback_arc_set）。
如果您可以放宽应用程序中对严格的最小解决方案大小的要求，还有其他可用的启发式方法，但它们可能难以相互比较。
请注意，您可以轻松找到最小（不是最小）解决方案：以任何顺序遍历任何反馈边缘集的边缘，如果冗余则立即删除。对所有边缘进行一次扫描就足够了，并使用例如 DFS 执行冗余测试。
对于任何反馈边，此图的补集必须是原始图的生成森林。这就是说补图不包含任何循环，这是非常明显的。
问题a)：
对于最小尺寸的反馈边集，这相当于找到最大尺寸的跨越森林。所以我们可以简单地使用 DFS 来找到图中每个连通分量的生成树并取补。然后我们得到一个最小尺寸反馈边。实际上，我认为 DFS 是没有必要的，只要我们可以为每个连接的组件找到一个生成树。
问题b)：
要找到一个最小权重反馈边集，这相当于找到最大权重跨越森林。然后我们可以使用 Kruskal 算法或 Prim 算法来找到每个连通分量的最大生成树。然后取补，我们将得到一个最小权重反馈集。
Your solution A) won't work because you don't provide any logic to decide wether an edge has a "back" property or not.
Your solution B) won't work because Kruskal doesn't look for a feedback set, but for a min-weighted covering tree. A good example of why a min-weighted tree doesn't necessarily include a feedback edge set is the K4 graph.