Graphy Theory Algorithm for minimally connecting areas with shared boundaries

Question

I have a weighted graph of multiple "animal pens" with each pen having at least 3 edges / points and at least two pens. I have to figure out the minimum weighted edges to remove in order to connect all pens (You can connect them by removing outer edges not connected to other pens too).

Can someone recommend an algorithm or a process with which I could approach finding the minimum weighted walls to remove. I was thinking about Prim's algorithm but I'm not even entirely sure how I could apply that.

This is problem S4 on http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

I don't want the answer just some direction as to how to approach it

Answer 1

You are in the right direction.

Model your problem as an undirected graph G=(V,E) where V = { all pens }, E = { (u,v) | there is a wall between u and v } with w((u,v)) = cost of wall between u and v

In order to "connect all pens" - you actually are looking for a subgraph: G'=(V,E') such that the sub graph G' will be connected [There is a path between every two nodes], and the cost of walls in E' are minimal.

To get this at minimal cost - you are looking for Minimum Spanning Tree. [It is easy to see that you indeed need a tree - because any extra edge after creating the tree is redundant and can be removed without harming the connectivity of the graph - or in the problem term - you can restore one wall and the pens will stay connected]

Two possible algorithms that will get you the MST are Prim and Kruskal