Grafos y Tablas de Hash




Universidad Simón Bolívar
Departamento de Computación y Tecnología de Información
Asignatura: Laboratorio de Algoritmos y Estructuras III
Sección: 1





INFORME PROYECTO 1:LABORATORIO DE ALGORITMOS Y ESTRUCTURAS III (CI-2693)














Grupo N° 19Rangel Jesus Orlando 09-10698



Caracas, noviembre2013

INFORME


El siguiente informe fue realizado con la finalidad de dar a conocer el programa a través del cual se obtiene la solución al proyecto 1 de la asignatura del Laboratorio deAlgoritmos y Estructuras III, el cual consiste en la implementación de un digrafo de acuerdo a un modelo que se adecue a los ordenes asintoticos especificados em un codigo base. El digrafo esta representadoem base a unas estructuras de listas, donde la estructura fundamental para su implementaciòn son unas tablas de hash, las cuales contienen los vértices y arcos agregados a dicha estructura. Ladecisión tomada para realizar el Digrafo como un Digrafo Hash, se basa principalmente en la eficiencia que brinda la estructura base ( Tabla de Hash) para el almacenamiento y la eliminación tanto de losarcos como de los nodos que posea el mismo; aparte de brindar mejoras em la eficiencia de las otras operaciones propias (pero mas especificas) que contiene todo grafo dirigido. Por medio de las tablas deHash, a traves de un hash code ( el cual es extraído del String que representan los vertices y nodos fuentes-destino de los arcos) se calcula la posición en la cual se deben almacenar los vertices yarcos, lo cual genera un orden constante de tiempo para agregar dichos elementos al digrafo. Para evittar colisiones dentro de la estructura implementada, cada posicion dentro de la tabla de Hash,...