Tarea 3 de Almacenamiento y Recuperación de la
Información
Trimestre 2009 Invierno
Entrega: 5 de marzo 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
pila. En otras palabras, cada vez que lea una arista de la entrada la
pondrá en los topes de pila correspondientes a sus dos
vértices y cada vez que desee obtener el siguiente vecino de un
vértice lo tomará del tope de la pila correspondiente.
Escribe un programa amplitudNN
que lea una gráfica y efectúe la búsqueda en
profundidad 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
pilas vacías (las cuales representaré como [], [], [],
[], [], [], [], []), al leer la primera arista (0, 1) las pilas quedan
[1], [0], [], [], [], [], [], [], al leer la segunda arista (1, 2) las
pilas quedan [1], [2, 0], [1], [], [], [], [], [] y así
sucesivamente hasta que al final las pilas quedan [3, 4, 1], [2, 0],
[3, 1], [0, 4, 2], [0, 3], [6], [7, 5], [6]. Como el algoritmo de
búsqueda en amplitud comienza visitando el vértice 0
entonces meterá a la cola a los vértices 3, 4 y 1 en ese
orden, luego se visita el vértice 3 el cual mete en la cola al
vértice 2 y así sucesivamente hasta que se termina de
visitar todos los vértices.