共享边界区域最小连通的图论算法

Question

我有一个多个“动物笔”的加权图，每个笔至少有3个边/点和至少两个笔。为了连接所有的笔，我必须找出要移除的最小加权边(你可以通过移除没有连接到其他笔的外边来连接它们)。

有人能推荐一种算法或过程吗?我可以用它来找到要移除的最小权重墙。我在考虑Prim的算法，但我甚至不完全确定如何应用它。

这是http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf上的problem S4

我不想要答案，只是想知道如何解决这个问题。

Answer 1

你的方向是对的。

将您的问题建模为无向图，其中V = { all pens }，E = { (u,v) | there is a wall between u and v } G=(V,E) w((u,v)) = cost of wall between u and v

为了“连接所有的笔”-你实际上是在寻找一个子图：G'=(V,E')使得子图G'将被连接每两个节点之间有一条路径，并且E‘中的墙的成本是最小的。

为了以最小的成本获得它-你正在寻找Minimum Spanning Tree。很容易看出您确实需要一棵树-因为创建树后的任何额外边都是多余的，并且可以在不损害图的连通性的情况下被移除-或者在问题术语中-您可以恢复一面墙，笔将保持连接

有两种可能的算法可以让你获得MST：Prim和Kruskal。