Geek Answers Handbook

Graph theory algorithm for minimally connected domains with common boundaries

I have a weighted graph of several “animal pens” with each pen having at least 3 edges / dots and at least two pens. I have to define the minimum weighted edges to remove in order to join all the handles (they can be joined by removing the outer edges that are not connected to other handles).

Can someone recommend an algorithm or process by which I could approach the search for minimally weighted walls for removal. I was thinking about the Prim algorithm, but I'm not even quite sure how I can apply this.

This is an S4 issue at http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/s SeniorEn.pdf

I don’t want the answer only in any direction regarding how to approach it

+5
source share
1 answer

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 }withw((u,v)) = cost of wall between u and v

To “connect all the handles” - you are really looking for a subgraph: G'=(V,E')so that an auxiliary graph will be connected G'[there is a path between every two nodes], and the cost of the walls in E 'is minimal.

- . [ , , - - , ]

, MST, Prim Kruskal

+5

More articles:


All Articles