el algoritmo de búsqueda en amplitud en una gráfica no dirigida.
Luis
15 de Mayo del 2010
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.
Escribir un programa que lea una gráfica y efectúe la búsqueda en profundidad de la misma.
La entrada al programa estará en un archivo 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 un archivo distinto a la entrada 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 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
8 8
0 1
1 2
2 3
3 4
4 0
0 3
5 6
6 7
Ejemplo de salida
0 1 4 3 2 5 6 7
Escribir un programa que lea una gráfica y efectúe la búsqueda en profundidad de la misma.
La entrada al programa estará en un archivo 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 un archivo distinto a la entrada 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 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
8 8
0 1
1 2
2 3
3 4
4 0
0 3
5 6
6 7
Ejemplo de salida
0 1 4 3 2 5 6 7
athena
25 de Junio del 2010
ayudennooooooooooooooooosssssssss por fa que alguien nos conteste por fas
