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]|v3 -> [5]|v6 -> [4,100]|v8 -> [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:
AdjList.py'; siga las convenciones de Python para la definición e implementación de los métodos init, eq y str.pydoc sobre la estructura de datos definida en AdjList.py.