在加权图中将循环图转换为非循环图

Question

我得到了一个连接的加权图，具有非负权重。我想将其转换为连接的无环图，以便最小化删除边缘的权重总和。输出将是删除的边缘。

我的想法：由于连接的无环图是一棵树，我可以简单地取最大n-1边，并删除所有其他边。但是，这可能并不总是正确的。这可能会导致图形断开连接。

然后，我想到了使用dfs。我知道如何使用 dfs 检测图形是否有循环，但我不知道如何检测所涉及的所有边以及如何将其转换为无环图。任何帮助(代码/伪代码/单词中的算法(将不胜感激。谢谢。。。

Answer 1

您需要最大生成树。使用 Kruskal 算法实现具有负权重的最小生成树。