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

Question

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

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

然后，我想到了使用dfs。我知道如何使用 dfs 检测图是否有循环，但我不知道如何检测所有涉及的边以及如何将其转换为非循环图。任何帮助（code/pseudocode/algo 文字）将不胜感激。谢谢...

Answer 1

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