CC30A Algoritmos y Estructuras de Datos

Tarea 1

Fecha de entrega: lunes 02 de octubre


Objetivos
 

El objetivo de esta tarea es implementar los algoritmos de árbol de expansión mínimo de un grafo Kruskal y Prim, y luego realizar una discusión en donde se comparen las ventajas y desventajas de un algoritmo sobre el otro.

Descripción de la tarea
 

El objetivo de los algoritmos de construcción del árbol de expansión mínimo de un grafo no direccional definido con pesos no negativos, es encontrar el árbol que conecte todos los nodos de un grafo (razón por la que es llamada "árbol de expansión") y que la suma del peso de los arcos sea la mínima (razón por la cual es llamado "mínimo").

Para mayor información sobre los algoritmos Kruskal y Prim, remítase a los apuntes de clases. También se tiene información en la bibliografía existente de algoritmos en la biblioteca central (revisen el Cormen y el Sedgewick).
 


Restricciones

  • El programa puede ser escrito utilizando uno de los siguientes lenguajes imperativos, disponibles en anakena.dcc.uchile.cl, cipres.cec.uchile.cl, o los computadores del Zocalo del CEC.
    1. C
    2. C++
    3. Java
    4. Pascal
    5. Turing
  • Para la implementación del algoritmo de Kruskal, deben implementar el algoritmo "Union Find".
  • Para la implementación del algoritmo de Prim, debe emplear un arreglo para controlar los costos.

  • Pruebas



    Entrega de la tarea
     
    La entrega de la tarea debe incluir un informe escrito donde se describa y documente el programa realizado, y se incluyan ejemplos de entradas y salidas.

    El informe debe ser entregado en la Secretaría Docente de Computación (donde la Magaly), y el código fuente (junto a un archivo README que explique como compilar) debe ser enviado utilizando el Cursomático de cc30a.

    El contenido del informe debe segir la siguiente pauta:
     

    Portada