令 G = (V,E) 为无向图。边的集合 F ⊆ E 称为 a 如果 G 的每个循环在 F 中至少有一条边，则设置反馈边。
(a) 假设 G 是未加权的。设计一个有效的算法来找到一个 最小尺寸反馈边集。
(b) 假设 G 是一个边权为正的带权无向图。 设计一种有效的算法来找到最小权重反馈边集。
我的解决方案(需要建议):
a) 最小尺寸反馈边集:由于图未加权，我们可以使用 DFS。我们像往常一样从任何顶点开始 DFS。当我们遇到后边时，我们将其插入到反馈边集中。当 DFS 完成时，集合将是答案。
b) 最小权重反馈边集:由于图是加权的，我们可以使用Kruskal。但是 Kruskal 通常从权重最小的边开始。如果我们可以否定所有边的权重，然后运行 Kruskal，每当我们在同一组件的顶点之间获得一条边时，我们就可以将其保存在反馈边集中。最后，否定边缘权重。我建议否定边缘权重的原因是因为我们需要最小权重反馈集。对于负权重，Kruskal 将从权重最小(实际上是最大)的边开始，然后为同一组件找到权重较小的边。
谁能告诉我这个解决方案是否正确？
最佳答案
是的，您的解决方案是正确的。无向图的最小权重反馈边集是最大权重生成森林的补充。所有生成林都具有相同的基数，因此在未加权的情况下，任何生成林(由 DFS 找到)都可以。 (证明草图:拟阵。)
反馈 arc 集确实是 NP-hard，但这是无向情况。
关于algorithm - 如何在无向图中找到反馈边集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10791689/