图论算法：最小连接具有共享边界的区域

Question

5

我有一张带权的多个“动物围栏”图，每个围栏至少有3条边/点和至少两个围栏。我必须找出要删除的最小加权边，以便连接所有围栏（您可以通过删除未连接到其他围栏的外部边缘来连接它们）。

有人能推荐一个算法或过程，我如何接近查找最小加权墙壁以删除。我考虑过Prim算法，但我甚至不确定如何应用它。

我不想得到答案，只是想知道如何解决它的方向。

- user1228643

1

最好在程序员交流网站上询问，这很可能会导致主观意见而不是客观事实的答案。 - Lazarus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

你正在朝着正确的方向前进。

将问题建模为一个无向图G=(V,E)，其中V = {所有笔}，E = {(u,v) | u和v之间有一堵墙}，并且w((u,v)) = u和v之间的墙的成本。

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

要以最小的成本获得这个结果 - 你需要寻找最小生成树。[很容易看出你确实需要一棵树 - 因为在创建树之后的任何额外边缘都是冗余的，并且可以删除而不会损害图的连通性 - 或者用问题术语来说 - 你可以恢复一堵墙，笔仍然保持连接]

可以使用两种可能的算法来获得MST：Prim和Kruskal。