图表中的最小损坏成本

给定一个图 G(V,E)，其中有 N 个节点（编号从 0 到 N-1）并且恰好为 (N-1)双向边缘.

图中的每条边都有一个正成本 C(u,v)（边缘权重）。

整个图是这样的任何一对节点之间都有唯一的路径

我认为改进的 Kruskal 是正确的选择。

取图G'=(V', E'), V'=V, E'={}。 按成本非递增顺序对 E 中的边进行排序。 现在，对于 E 中的每条边，将其添加到 E' 中，前提是它不连接两个都具有带有炸弹顶点的组件。 结果是E-E'的成本之和。

EDIT:

在你的例子上运行这个。

最初，我们的边集是空的 {}，我们将边按非递增顺序排序 [(1, 2), (0, 1), (2, 4), (1, 3)]

因此，一开始，我们的图表由 5 个不相连的组件组成。

(1, 2) 的成本为 8，并且它连接的组件中只有一个有炸弹。所以我们将它添加到 E' 中。 E'={(1, 2)}，我们有 4 个分量。

下一个最高成本边是 (0, 1)，成本为 5。但是两个组件都有炸弹，因此不要添加此边。

下一个是 (2, 4)。这也连接到带有炸弹的组件，所以我们也跳过这一点。

最后，最低成本边是 (1, 3)。由于其组件之一（仅包含节点 3）没有炸弹，因此我们将其添加到 E'。

由此得出 E' = {(1,2), (1, 3)}。

我的推理是，我们尝试在成本较低的边之前添加成本较高的边 - 这确保了在原始节点中带有炸弹的节点之间的任何路径中，除了最低成本之外的所有边都会被添加。