Estructura de Datos y Algoritmos
1er. Sem 2004
Tarea 5: Árbol de expansión mínima
El objetivo de esta tarea es
ejercitar el manejo de grafos, su representación y la
programación de algortimos para obtener el árbol de
expansión mínima.
Contexto: La zona austral de Chile se está poblando y las
comunidades de esas localidades se organizan para tener conexión
por fibra óptica entre ellas y desde una de ellas hacia el resto
del planeta. Parte del estudio considera la solución que
minimiza el costo del proyecto total de tendido de fibra. Se tiene el
costo de conectar pares de localidades y se busca identificar
cuáles de esas conexiones deberian formar parte de la
solución de costo mínimo.
Usted desarrollará la herramienta de tipo general. Como entrada
tendrá todas las conexiones (arcos) de interés y las
localidades (vértices). Asociado a cada arco se tiene el costo
de implementar esa conexión. Como salida se pide el listado de
conexiones y el costo mínimo del proyecto.
Desarrolle el programa conectividad.
>$ conectividad <nombre_de_archivo_de_entrada>
El programa nos permite obtener el "árbol de expansión
mínima". El grafo
será ingresado vía el archivo especificado como
argumento. La
salida del programa será la lista de arcos que componen la
solución y el costo del árbol (suma de los pesos de sus
arcos).
Formato de entrada
El formato del archivo de entrada es:
{<número entero> <número entero> <peso>
CR}+
/* CR = Carrier return o Retorno de carro o enter, */
Por ejemplo:
0 1 0.41
1 2 0.51
2 3 0.50
4 3 0.36
3 5 0.38
3 0 0.45
0 5 0.29
5 4 0.21
1 4 0.32
4 2 0.32
5 1 0.29
Formato de salida
El formato de salida en consola es:
"El costo del árbol: " <valor> CR
"y está compuesto por los arcos:" CR
{<número entero> <número entero> <peso>
CR}+
Recomendación
Si opta por una implementación del algoritmo de PRIM, se acepta
por simplicidad que utilice arreglo(s) simple como estructura de datos
para implementar la cola de prioridad. En este caso el mínimo lo
obtiene usted en costo O(n) recorriendo todos los elementos del arreglo
y buscando el mínimo.