用DFS设置最小权反馈边？

Question

算法设计手册中的练习

6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.

我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。

Answer 1

以下是我如何处理这个问题的方法。

为了简单起见，让我们假设G是连通的(下面描述的算法可以很容易地扩展到G不连通的情况下)。

首先，对于任何反馈边集F，图G‘= (V，E)都不存在圈。这直接来自反馈边集的定义.

由于我们正在寻找具有最小总重量的集合F，G‘应该是一棵树，而G’中的边必须有最大的总重量(为什么?)

→G‘必须是一个最大生成树。

因此，现在把原来的问题归结为寻找一个最大生成树。您可能已经知道，Kruskal的算法可以用于寻找最小生成树。只要稍加修改，您就可以使用Kruskal的算法找到一个最大生成树。https://stackoverflow.com/questions/4992664/how-to-find-maximum-spanning-tree

因此，最后，我刚才描述的算法的运行时间为O(E log V)时间(这正是Kruskal算法的运行时间)。

Answer 2

实际上，不，一个反例：

A --10-- B -- 10 -- C
          \        /
           6     4
            \   /
              D

外勤部将这样做：

-> B -> C -> D

该图的最小反馈边将成为树的边缘。