Tarea 3 de Almacenamiento y Recuperación de la
Información
Trimestre 2013 Invierno
Entrega: 18 de febrero 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.