graph - 如何获取最小权重连接子集

Question

这是一个消费税：

考虑从加权连接图 G 中查找边的最小权重连接子集 T 的问题。T 的权重是 T 中所有边权重的总和.给出一种有效的算法来计算最小权重连接子集 T。

这是我得到的：

1. 我必须假设权重由正负权重混合。只有两种重量的混合才能对这种消费税有意义。

2. 我将首先对边缘进行排序，因此负边缘将排在第一位。

3. 我会考虑使用 Kruskal 的算法，但应该进行一些修改

4. 因为我欢迎负面边缘，所以我会尝试添加尽可能多的负面边缘。

此外，可以添加一些正边，以防

5. 并非所有负边都连接起来，并且它们可能需要一些正边作为桥梁。

---

好的，以上是我的想法。但是当我试图弄脏我的手时，我被卡住了。

如何始终记录可能的最小称量值设置？

例如

{0， 1} 的权重为 -20

{2， 3} 的权重为 -10

如果 {1， 3} 的权重为 11，那么我当然不想要 {1， 3}

或者如果 {1， 3} 的权重为 9，那么我想要

使用哪种数据结构，我始终可以保持最小权重和该权重的顶点？

---

值得注意的是，该消费税寻求的子集旨在edges。

考虑查找最小权重连接子集 T 的问题 加权连接图 G 中的边

这意味着仍然需要包含所有顶点。

此外，它不仅仅是一个MST。考虑如果顶点有两个边，一条是 -1，另一条是 -2。在正常的 MST 算法中，只会采用 -2 的边。但是在这个消费税中，需要采取-1和-2来进一步减轻整体重量。

Answer 1

我认为您的算法已经基本正确，但是稍作修改，实现起来就变得微不足道了。

首先，必须包括每个负边，以最小化产生的重量。接下来，计算c连接的组件数。如果c=1，你就完成了。否则，您需要额外的c-1正边缘。

现在，当您添加负边时，请将其视为 Kruskal 的算法过程。每一个负面的边缘都可能将克鲁斯卡尔森林中的几棵树联合起来。但是，即使负边的末端属于 Kruskal 森林中的同一棵树，您也可以添加负边 - 这与通常的 Kruskal 算法不同，在通常的 Kruskal 算法中，您只添加连接两棵不同树的那些边。

在此阶段之后，您将看到c连接的组件的图形(它们可能不再是树(。现在只需像往常一样继续 Kruskal 的算法。按递增顺序处理正边，跟踪使用正边建立的并集数。一旦这个数字达到c-1，你就完成了。

顺便说一下，如果你将森林表示为不相交集数据结构，Kruskal 算法的所有过程都可以轻松实现。它只需要几行代码来编写，之后跟踪所做的联合数量是微不足道的。

---

一些伪代码如下：

sort(edges);
c := n;
for edge in edges:
    if edge.weight < 0:
        if find(edge.firstEnd) != find(edge.secondEnd):
            --c;
        unite(edge.firstEnd, edge.secondEnd);
    else:
        if c == 1: break;
        if find(edge.firstEnd) != find(edge.secondEnd):
            unite(edge.firstEnd, edge.secondEnd);
            --c;

这里unite和find是不相交集数据结构的功能。