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

Question

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

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

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

Answer 1

您需要最大生成树。使用 Kruskal 算法获得具有否定权重的最小生成树。