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.

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

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

它也不仅仅是一个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是并查集的功能.