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.