Laboratorio 8: Listas de adyacencia

Post date: Mar 15, 2013 5:02:01 PM

Una lista de adyacencia es una estructura de datos bidimensional que permite búsquedas e inserciones eficientes y, a su vez, es óptima en el uso de memoria. Uno de sus principales usos es en la representación de relaciones binarias (o grafos) y la representación de listas con prioridad.

En particular, la estructura de datos lista de adyacencia ofrece las siguientes operaciones:

  • init(): crea una lista de adyacencia vacia (complejidad temporal O(1))
  • eq(other): determina si la lista de adyacencia es igual a other (complejidad temporal O(n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • str(): representación en cadena de la lista de adyacencia (complejidad temporal O(n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • insert(x,y): inserta el elemento y con prioridad x (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • contains(x,y): retorna True si el elemento y con prioridad x está en la lista de adyacencia; False de lo contrario (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)
  • remove(x,y): elimina el elemento y con prioridad x de la lista de adyacencia, si este existe (complejidad temporal O(log2 n), en donde n es la cantidad de elementos en la lista de adyacencia)

Dadas las restricciones en la complejidad temporal para las funciones insert, contains y remove, es imperativo utilizar estructuras de datos ordenadas para poder efectuar búsquedas binarias sobre la lista de adyacencia. En particular, representaremos internamente una lista de adyacencia como una lista encadenada lista de Python (list()) de listas encadenadas listas de Python, en donde cada una de las listas está ordenada ascendentemente. Asumiremos que los elementos almacenados en una lista de adyacencia serán números enteros y que la prioridad también es un número entero.

Por ejemplo, el siguiente esquema brinda una representación gráfica de una lista de adyacencia que contiene los elementos (1,2),(3,5),(1,0),(8,7),(6,4),(6,100),(1,0):

1 -> [0,2]
|
v
3 -> [5]
|
v
6 -> [4,100]
|
v
8 -> [7]

Note que tanto las prioridades (1,3,6,8) como los valores asociados a cada una de ellas están ordenados ascendentemente. Además note que ninguna pareja está repetida!

En internet existen muchas fuentes de información sobre el algorítmo de búsqueda binaria para para estructuras lineales y ordenadas (es más, este algoritmo fue parte del primer quiz del semestre ... recuerdan?). En particular, pueden consultar las siguientes páginas para repasar el tema:

El laboratorio es individual y cada estudiante debe entregar:

  • El código impreso del laboratorio en un archivo llamado 'AdjList.py'; siga las convenciones de Python para la definición e implementación de los métodos init, eq y str.
    • El encabezado del archivo debe indicar, usando comentarios de Python,
      • Su nombre en la primera línea
      • Su código de estudiante en la segunda línea
  • La estructura de datos debe estar debidamente documentada. Para ello, debe entregar impreso el texto que se obtiene al ejecutar el comando pydoc sobre la estructura de datos definida en AdjList.py.
  • El código impreso de las pruebas hechas para validar la estructura de datos lista de adyacencia; cada método de la estructura de datos debe probarse con al menos 5 casos de prueba diferentes.
  • El resultado impreso de ejectuar las pruebas para cada uno de los métodos de la estructura de datos lista de adyacencia.