blocks|key|2048319|text|您的解决方案A)将无法工作，因为您没有提供任何逻辑来确定边缘是否有“后退”属性。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2048320|你的解决方案B)不能工作，因为Kruskal不寻找反馈集，而是寻找一个最小加权覆盖树。K4图是一个很好的例子，说明了为什么最小加权树不一定包含反馈边缘集。|2048321|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

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.

blocks|key|2903609|text|这两个问题都是NP-完全的。因此，即使是近似有效的(多项式时间)解也不可能存在(http://en.wikipedia.org/wiki/Feedback_arc_set).|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2903610|如果您可以放宽对应用程序中严格的最小解决方案大小的要求，那么还可以使用其他启发式方法，但它们之间可能很难进行比较。|2903611|请注意，您可以很容易地找到最小(非最小)的解决方案:以任何顺序遍历任何反馈边集的边缘，如果红色，则立即删除。一次扫描所有边缘是足够的，并执行冗余测试使用，例如，DFS。|2903612|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Feedback/_arc/_set^0|14|19|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

Both problems are NP-complete. Therefore, even approximate efficient (polynomial-time) solutions are unlikely to exist (http://en.wikipedia.org/wiki/Feedback_arc_set).

If you can relax the requirement for the strict minimum solution size in your application, there are other heuristics available, but they may be difficult to compare against each other. 

Note that you can easily find minimal (not minimum) solutions: Go through the edges of any feedback edge set in any order, and remove immediately if redunant. One sweep over all edges is sufficient, and perform the redundancy test using, e.g., DFS.

blocks|key|2025659|text|是的，你的解决方案是正确的。无向图的最小权反馈边集是最大权生成森林的补充.所有的生成森林都具有相同的基数，因此在未加权的情况下，任何生成林(如DFS所发现的)都可以。(校样素描:拟阵)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2025660|反馈弧集确实是NP-硬的，但这是无向情况。|2025661|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Yes, your solution is correct. Minimum-weight feedback edge sets of undirected graphs are complements of maximum-weight spanning forests. All spanning forests have the same cardinality, so in the unweighted case any spanning forest (as found by DFS) will do. (Proof sketch: matroids.)

Feedback arc set is indeed NP-hard, but this is the undirected case.

blocks|key|2025691|text|要在具有正权重的加权有向图中找到最小权反馈边集：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2025692|通过否定权值，观察到它等价于寻找最大权反馈边集.若要找到最大权重反馈边缘集，请使用Prim或Kruskal算法构建MST。那就拿MST的补品。|2025693|为什么会起作用？这是基于以下意见：|2025694|边不是在任何MST中的当且仅当存在一个循环时，该边对该循环中的所有其他边都有最大的权重。或者换句话说，边在某些MST中是当且仅当对于该边所属的每个循环，它都不是该周期中所有其他边的最大权重。|offset|length|style|BOLD|2025695|实际上，假设我们有一个带有边的最大权反馈边集，这样就存在一个包含该边和另一个边具有更大权重的循环，然后用另一个边替换该边将提供一个更大权重的反馈边集。|2025696|为了完整起见，可以使用一个证明来证明该观察：|2025697|(+<=)假设一个边在一个循环中具有最大的权重。如果它在某些MST中，那么用该周期中的另一个边缘来替换它将提供一个重量较小的MST。|2025698|(+=>)假设对于给定边所属的每一个循环，该循环中都存在一个具有较大权重的边。如果它不在任何MST中，那么将该边缘添加到MST中将导致MST中的循环。然后，从该周期(与给定的边缘不同)去除最大权重的边缘将提供具有较小权重的MST+(并包含该给定的边缘)。|2025699|entityMap^0|0|0|0|0|18|0|0|D|2|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Y|8|@$H|Z|I|10|J|K]]|9|@]|A|$]]|$1|L|3|M|5|6|7|11|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|12|8|@$H|13|I|14|J|K]]|9|@]|A|$]]|$1|P|3|Q|5|6|7|15|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|16|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|U|$]]

To find a minimum-weight feedback edge set in a weighted digraph with positive weights:

By negating the weights, observe that it is equivalent to finding the maximum-weight feedback edge set.
To find a maximum-weight feedback edge set, build an MST using either Prim's or Kruskal's algorithm. Then take the complement of that MST.

Why does it work?
This is based on the following observation:

An edge is not in any MST if and only if there exists a cycle for which that edge has the maximum weight over all other edges in that cycle.
Or, in other words, an edge is in some MST if and only if for every cycle to which that edge belongs, it is not of maximum weight over all other edges in that cycle.

Indeed, assume we have a maximum-weight feedback edge set with an edge such that there exists a cycle comprising that edge and another edge with greater weight, then replacing that edge with this other edge would provide a feedback edge set of greater weight.

For completeness, a proof of the observation:

&lt;=) Suppose an edge has the maximum weight in a cycle. If it were in some MST, then replacing that edge with another edge from that cycle would provide an MST with smaller weight.

=>) Suppose that for every cycle to which a given edge belongs, there exists an edge with greater weight in that cycle. If it is not in any MST, then adding that edge to an MST would cause a cycle in an MST. Then removing the edge of maximum weight from that cycle (which is different from the given edge) would provide an MST with smaller weight (and comprising that given edge).

blocks|key|2025707|text|对于任何反馈边，该图的补必须是原始图的生成林。这就是说补图不包含任何循环，这是非常明显的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2025708|问题a)：|2025709|对于最小大小反馈边集，这相当于找到最大跨越森林的大小。因此，我们可以简单地使用DFS为图的每个连通部分找到生成树，并取补。然后得到最小大小反馈边。实际上，我认为DFS是不必要的，只要我们能为每个连接的组件找到一个生成树。|2025710|问题b)：|2025711|要找到最小权重反馈边集，这相当于寻找最大权重跨越森林。然后，我们可以使用Kruskal算法或Prim算法找到每个连通分量的最大生成树。然后取补码，我们将得到一个最小权重反馈集。|2025712|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

For any feed-back edge, the complement of this graph must be a spanning forests of the original graph. This is to say that the complement graph doen't contain any cycle, which is very obvious.

Problem a): 
For a minimum size feedback edge set, this is equivalent to find the maximum size spanning forests. So we can simply use DFS to find the spanning tree for each connected components of the graph and take the complement. Then we get a minimum size feedback edge. Actually, I think DFS is not necessary, as long as we can find for each connected components a spanning tree. 
Problem b): 
To find a minimum weighgt feedback edge set, this is equivalent to find the maximum weight spanning forests. Then we can use the Kruskal algorithm or Prim's algorithm to find the maximum spanning tree for each connected components. Then take the complement and we will get a minimum weight feedback set.

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a
feedback-edge set if every cycle of G has at least one edge in F.

(a) Suppose that G is unweighted. Design an efficient algorithm to find a
minimum-size feedback-edge set.

(b) Suppose that G is a weighted undirected graph with positive edge weights.
Design an efficient algorithm to find a minimum-weight feedback-edge set.

<hr>

My solution (need suggestions):

a) Minimum size feedback edge set: since the graph is unweighted, we can use DFS. We start DFS from any vertex as usual. When we encounter a back edge, we insert it into set of feedback edges. When DFS completes, the set will be the answer.

b) Minimum weight feedback edge set: since the graph is weighted, we can use Kruskal. But Kruskal normally starts with edge of smallest weight. If we can negate all edge weights, and then run Kruskal, whenever we get an edge between vertices of same component, we can save that in feedback edge set. In the end, negate edge weights. The reason I propose to negate edge weights is because we need minimum weight feedback set. With negated weights, Kruskal will start with edges with smallest weight (actually largest), and will find edges for same component with smaller weights.

Can someone tell if this solution is correct?

How to find feedback edge set in undirected graph

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

设G= (V，E)是无向图。若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。(a)假设G未加权。设计了一种有效的求最小大小反馈边缘集的算法.(b)设G是一个具有正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.我的解决方案(需要建议)：( a) 最小大小反馈边集：，由于图是不加权的，我们可以使...

问如何在无向图中寻找反馈边集
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在无向图中寻找反馈边集EN