4

这是一个消费税：

考虑从加权连通图 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。

考虑从加权连通图 G中找到最小权重连通子集 T 的问题

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

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

4

1 回答 1

7

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

首先，必须包含每个负边缘以最小化最终的权重。接下来，计算连通分量的数量c。如果c=1，你就完成了。否则你需要额外的c-1积极边缘。

现在，当您添加负边缘时，已将其视为 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是不相交集数据结构的功能。

于 2012-05-02T22:38:27.037 回答