Tarea 2 de Almacenamiento y Recuperación de la Información

Trimestre 2010 Primavera
Entrega: 21 de mayo a las 22:00.

El propósito de esta tarea es el de practicar el algoritmo de búsqueda en amplitud en una gráfica no dirigida.

Sea G = (V, E) una gráfica con N vértices (numerados del 0 al N-1) y M aristas (que unen a dos vértices distintos). Implemente el algoritmo de búsqueda en amplitud visto en clase de modo que la estructura de datos que representa a la gráfica sea la de listas de adyacencia y donde cada lista de adyacencia es una cola. En otras palabras, cada vez que lea una arista de la entrada la pondrá al final de las colas correspondientes a sus dos vértices y cada vez que desee obtener el siguiente vecino de un vértice lo tomará del frente de la cola correspondiente.

Escribe un programa amplitudNN que lea una gráfica y efectúe la búsqueda en amplitud de la misma, donde NN son los dos dí­gitos de la clave que le fue proporcionada por el profesor.

La entrada al programa estará en el archivo amplitud.ent y consiste de un renglón con dos entero N y M (la cantidad de vértices y aristas de G) seguido de M renglones con 2 enteros U y V cada uno (los dos vértices unidos por cada arista de G). Puedes suponer que 1 <= N <= 100 y que todas las aristas son distintas.

La salida del programa deberá estar en el archivo amplitud.sal y consiste de un renglón con N enteros V1, V2, ..., VN (los vértices de G en el orden en el que son visitados por el algoritmo).

Ejemplo

Si tomamos el ejemplo de entrada mostrado en la página 147 de las notas de clase entonces las listas de adyacencia comienzan siendo 8 colas vacías (las cuales representaré como [], [], [], [], [], [], [], []), al leer la primera arista (0, 1) las colas quedan [1], [0], [], [], [], [], [], [], al leer la segunda arista (1, 2) las colas quedan [1], [0, 2], [1], [], [], [], [], [] y así sucesivamente hasta que al final las colas quedan [1, 4, 3], [0, 2], [1, 3], [2, 4, 0], [3, 0], [6], [5, 7], [6]. Como el algoritmo de búsqueda en amplitud comienza visitando el vértice 0 entonces meterá en su cola los vértices 1, 4, 3 en ese orden, luego se visita el vértice 1 el cual mete en la cola al vértice 2 y así sucesivamente hasta que se termina de visitar todos los vértices.

Ejemplo de entrada
Ejemplo de salida
8 8
0 1
1 2
2 3
3 4
4 0
0 3
5 6
6 7
0 1 4 3 2 5 6 7