Buenas tardes, tenia dudas de si el algoritmo que pensé para la parte a) de este ejercicio estaba bien, estuve pensándolo mucho y al final llegue a esto, antes de avanzar a demostrar en la parte b) quería saber si estaba encaminada o no.
hola rocío,
comenzando por el final. la reconstrucción del camino (a partir de una recorrida BFS) debe basarse en el hecho de encontrar el ancestro común de u y v. esto debe ser acompañado por el hecho que u y v pueden no pertenecer al mismo nivel (ver K&T 3.4) y debemos realizar acciones "compensatorias" cuando esto ocurre para que los dos "punteros" que voy considerando siempre estén al mismo nivel mientras voy subiendo en el árbol camino al ancestro común. Otro detalle es que, la arista (u,v) es la primera arista del ciclo que detecto y agrego (esto lo hacés). luego, si consideramos una estructura lineal que nos permita recorrer el ciclo al final, hay que ir agregando los padres de u y v a cada lado (der, izq) hasta llegar al ancestro común para que la secuencia de nodos quede en orden.
sobre el BFS propiamente, un detalle nomás, no incrementás el i.
comenzando por el final. la reconstrucción del camino (a partir de una recorrida BFS) debe basarse en el hecho de encontrar el ancestro común de u y v. esto debe ser acompañado por el hecho que u y v pueden no pertenecer al mismo nivel (ver K&T 3.4) y debemos realizar acciones "compensatorias" cuando esto ocurre para que los dos "punteros" que voy considerando siempre estén al mismo nivel mientras voy subiendo en el árbol camino al ancestro común. Otro detalle es que, la arista (u,v) es la primera arista del ciclo que detecto y agrego (esto lo hacés). luego, si consideramos una estructura lineal que nos permita recorrer el ciclo al final, hay que ir agregando los padres de u y v a cada lado (der, izq) hasta llegar al ancestro común para que la secuencia de nodos quede en orden.
sobre el BFS propiamente, un detalle nomás, no incrementás el i.
Hola facundo, muchas gracias por la respuesta, voy a ver si soluciono eso y cualquier cosa pregunto, la otra duda que me surgió, que pasa si el grafo G que me dan no es conexo debería buscar en cada componente conexa no? Cosa que ahí no hago
correcto, como no se asegura lo contrario, G es un grafo "cualquiera" y puede ser no conexo (tener varias componentes). en ese caso hay que buscar el ciclo en cada una utilizando la misma estrategia.
Hola!! Termine haciendo esto, me tranque en la parte del reciproco de la demostración de la corrección, y en realidad no se muy bien si lo que demostré es realmente valido, si me podrían decir como puedo encarar el reciproco .Muchas gracias!!
hola rocío,
comento cositas por partes:
1- parte a) en las líneas 14-22, dónde buscás identificar si u,v están en el mismo nivel. dado que el ciclo se cierra al encontrar a v, el único que puede estar a lo sumo un nivel más arriba es justamente v, no u. es decir, las posibilidades son que u y v estén en el mismo nivel o que v esté en el nivel anterior (superior en T).
2- parte b) el directo debería comenzar a partir del hecho b=true pero derivás rápidamente en que el alg devuelve ciclo no NULL. debieras ir paso a paso. p.ej. si b=true, identificar que ello sólo ocurre en la línea10, entonces encontramos v=padre[u] (por K&T 3.4 y 3.7) formando un ciclo. lo que sigue está bien.
para el recíproco, debemos partir, ahora sí de haber retornado un ciclo no NULL. nuevamente, partimos de identificar que en la línea 11 se inicializa el ciclo con el agregado de la primera arista. simultaneamente se asigna b=true y no existe otra secuencia de ejecución posterior que opere en la dirección contraria. de modo que a partir de ello el ciclo se construye y retorna.
saludos
comento cositas por partes:
1- parte a) en las líneas 14-22, dónde buscás identificar si u,v están en el mismo nivel. dado que el ciclo se cierra al encontrar a v, el único que puede estar a lo sumo un nivel más arriba es justamente v, no u. es decir, las posibilidades son que u y v estén en el mismo nivel o que v esté en el nivel anterior (superior en T).
2- parte b) el directo debería comenzar a partir del hecho b=true pero derivás rápidamente en que el alg devuelve ciclo no NULL. debieras ir paso a paso. p.ej. si b=true, identificar que ello sólo ocurre en la línea10, entonces encontramos v=padre[u] (por K&T 3.4 y 3.7) formando un ciclo. lo que sigue está bien.
para el recíproco, debemos partir, ahora sí de haber retornado un ciclo no NULL. nuevamente, partimos de identificar que en la línea 11 se inicializa el ciclo con el agregado de la primera arista. simultaneamente se asigna b=true y no existe otra secuencia de ejecución posterior que opere en la dirección contraria. de modo que a partir de ello el ciclo se construye y retorna.
saludos
Hola, muchas graciass, ahora quedo todo claro
Saludos
Saludos