Ejercicio 1.C - Calentamiento P3

Ejercicio 1.C - Calentamiento P3

de Marco Liguori Hernandez -
Número de respuestas: 3

Buenas,

En este ejercicio me queda la duda de "como" debería devolver las colecciones de nodos. Primero que nada, me parece que el algoritmo de BFS, que trabaja por capas el grafo, debería ser el mejor para tratar el problema. Luego, ¿habría alguna diferencia con lo que devuelve el algoritmo de BFS implementado con listas de adyacencia que muestra el libro?. Dado que ese algoritmo justamente muestra una implementación, quizás lo que pide este ejercicio es algo más abstracto, pero no veo como hacerlo. 

Desde ya muchas gracias,

Marco.

tbfs listas de ady

En respuesta a Marco Liguori Hernandez

Re: Ejercicio 1.C - Calentamiento P3

de Facundo Benavides -
hola marco,
es justamente por ahí. el algoritmo presentando retorna la componente conexa como un árbol que tiene a 's' como raíz. y lo hace apoyándose en estructuras auxiliares como las capas L.
en este caso lo que se pide son las capas =D
saludos
En respuesta a Facundo Benavides

Re: Ejercicio 1.C - Calentamiento P3

de Marco Liguori Hernandez -
Buenas Facundo,

¿Un algoritmo así sería válido para resolver el problema?,

capasDeG(s):
   Discovered[s] = true and Discovered[v] = false para todos los otros nodos v
   Inicializo L[0] = s
   Seteo contador de capas i=0

   While L[i] no está vacío
       Inicializo una lista vacía L[i+1]
       For each nodo u en L[i]
            Considero cada arista (u,v) incidente a u
            If Discovered[v] = false then
               Seteo Discovered[v] = true
               Añado v a L[i+1]
            EndIf
        EndFor
        Incremento contador de capas i = i + 1
   EndWhile
End

En este caso retorno el array L que tendría por cada i, los nodos correspondientes a esa capa en particular.

Desde ya muchas gracias, Marco.