Algoritmo de teoría de gráficas para conectar áreas con límites compartidos

Question

Tengo un gráfico ponderado de múltiples "plumas de animales" con cada pluma con al menos 3 bordes/puntos y al menos dos plumas. Tengo que descubrir los bordes ponderados mínimos para eliminar para conectar todos los bolígrafos (Puede conectarlos quitando los bordes externos que no están conectados a otros lápices también).

¿Alguien puede recomendar un algoritmo o un proceso con el que podría abordar la búsqueda de las paredes ponderadas mínimas para eliminar. Estaba pensando en el algoritmo de Prim, pero ni siquiera estoy del todo seguro de cómo podría aplicar eso.

Este es un problema S4 en http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

no quiero la respuesta sólo algunas dirección en cuanto a la manera de acercarse a ella

Answer 1

Usted está en la dirección correcta.

Modelo su problema como un grafo no dirigido G=(V,E) donde V = { all pens }, E = { (u,v) | there is a wall between u and v } con w((u,v)) = cost of wall between u and v

Con el fin de "conectar todas las plumas" - que realmente están buscando un subgrafo: G'=(V,E') tal que la gráfica sub G' se conectará [ Hay un camino entre cada dos nodos], y el costo de las paredes en E 'es mínimo.

Para obtener esto a un costo mínimo, usted está buscando Minimum Spanning Tree. [Es fácil ver que realmente necesita un árbol, ya que cualquier ventaja adicional después de crear el árbol es redundante y puede eliminarse sin dañar la conectividad del gráfico, o en el término del problema, puede restaurar una pared y las plumas CASA]

Dos algoritmos posibles que les permite conocer el MST son Prim y Kruskal