如何在无向图中寻找反馈边集
设G=(V,E）是无向图。如果G的每个圈在F中至少有一条边，则称边集F E为反馈边集。
a）最小尺寸反馈边集：由于图是无权的，我们可以使用DFS。我们像往常一样从任意顶点开始DFS。当我们遇到一个后边时，我们将它插入反馈边集。当DFS完成时，该集将是答案。
b）最小权重反馈边集：由于图是加权的，我们可以使用Kruskal。但是Kruskal通常从最小权重的边开始。如果我们可以否定所有的边权重，然后运行Kruskal，每当我们在同一分量的顶点之间得到一条边，我们就可以将它保存在反馈边集中。最后，否定边权重。我建议否定边权重的原因是因为我们需要最小权重反馈集。在否定权重的情况下，Kruskal将从最小权重（实际上是最大的）的边开始，并且将为相同分量找到权重较小的边。
有人能说出这个解决方案是否正确吗？
共有1个答案
是的，你的解决方案是正确的。无向图的最小权反馈边集是最大权生成森林的补充。所有跨林都具有相同的基数，因此在未加权的情况下，任何跨林（如DFS所发现的）都可以。（证明草图：拟阵。）
反馈弧集确实是NP难的，但这是无向的情况。
-
我试着用谷歌搜索，但是没有任何有价值的东西弹出。 图表： 它是无方向的 表示为具有双边的有向图 可能包含具有负权重的边 我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小 此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。
-
我在Python3中有一个简单的代码，使用igraph返回我添加到无向图中的边。 但是，如果按照输入源和目标的顺序设置源和目标，它会返回边缘。在这种情况下，源=0，目标=1 我的猜测是，它不是真正的无向图。 我的问题是，如何得到一个真正的无向图，即使我在g.es.find（）函数中切换了源节点和目标节点，它也会返回边，就像对无向图一样？
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
注意，有一个多边形ABCIHGJKLMLKA，它包括节点KLM，但多边形CDEG不包括F。 我读过关于这个问题的解决方案，但没有像我这样的leaf要求。在以前的解决方案中存在的一些公理是，每条边只使用两次，但是死端边总共需要遍历四次。也就是说，存在一个包含所有外部节点ABCDEFGJKLMLKA的多边形，但是它会被丢弃，因为它将朝外。 下面介绍了一种类似问题的解决方案，即sans the leaf
-
假定给定一个给定图G（有n个顶点和m条边）的最小生成树T和一个新边e=(u,v）,它的权重为w。 （I）检验T是否为MST；（II）如果不是，给出了求图G+E的最小生成树的有效算法。
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。