ej 2 semana 4

ej 2 semana 4

de Bruno Stefano Lombardo Palleiro -
Número de respuestas: 7

Buenas, hice este algoritmo pero en la parte en que devuelve un ciclo creo que no estoy devolviendo uno, el último while es para eliminar los nodos que quedaron pero que no forman parte del ciclo, pero creo que en algunos casos borro nodos que pertenecen al ciclo ya que u puede ser cualquier nodo y entonces no necesariamente los últimos nodos de "ciclo" son los que tengo que eliminar.

Además, me parece que cuando tomo el primer nodo u  y dentro del penúltimo while tendría que exigir que u este activo.

Saludos


Adjunto WhatsApp Image 2021-08-31 at 4.19.01 PM.jpeg
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej 2 semana 4

de Facundo Benavides -
hola bruno,
empezando por lo último, diría que no. el arreglo activos cumple la función de señarte que no encontraste un OT. luego para la parte de reconstruir el ciclo, utilizás visitados, y potencialmente, participan todos los vértices en la búsqueda, eso es correcto.
sobre el úlitmo while donde "eliminás" vertices. confieso que no entiendo bien la motivación. en el ciclo que vas construyendo no hay nada que sobre y por tanto nada a eliminar. simplemente, lo que no se agregan no son parte del ciclo y listo.
saludos
En respuesta a Facundo Benavides

Re: ej 2 semana 4

de Bruno Stefano Lombardo Palleiro -
Buenas,
Entonces para que el código esté bien, tendría que eliminar el último while nomás?
igual sigo con dudas, porque yo se que los nodos que siguen activos luego del primer while tienen todos aristas entrantes, entonces, siguiendo hacía atrás sólo los activos, no construiría un ciclo? Que es el detalle que te decía.
Con esto en cuenta veo que el último while es innecesario, es correcto?
saludos
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej 2 semana 4

de Facundo Benavides -
hola,
creo que ahora entendí lo que intentabas hacer. rebobinemos un poco.
esto que decías "Además, me parece que cuando tomo el primer nodo u y dentro del penúltimo while tendría que exigir que u este activo." es correcto y por tanto esto que respondí antes "y potencialmente, participan todos los vértices en la búsqueda" es incorrecto.
quizás sea bueno notar que si recorro los nodos activos "en reversa" siempre encuentro un ciclo. lo otro es que u se va actualizando. en verdad no nos importa cuál nodo fue el primero que tomamos para realizar esta recorrida (podría no pertenecer al ciclo), pero si nos importa saber cuál es el u que cierra el ciclo. y ese es el primer "ya visitado". desde ese u puedo recomponer el ciclo.
por tanto, en lugar de agregar todos al ciclo y luego intentar eliminar (ahora entendí que estabas queriendo hacer), simplemente podés construir el ciclo al final a partir del último u hacia atrás.
espero ahora se entienda.
saludos
En respuesta a Facundo Benavides

Re: ej 2 semana 4

de Bruno Stefano Lombardo Palleiro -
Hola, entiendo la idea.
En vez de ir agregándolo como lo hice yo, podría hacer un nuevo while, e ir recorriendo hacía atrás empezando desde ese u y ahí si creo el ciclo.
Tendría que exigir que en este nuevo while que los nodos en los que voy pasando ya hayan sido visitados no? porque me hice unos ejemplos en papel y vi que si hay algún nodo que tiene mas de una arista entrante se me puede desviar fuera del ciclo. Pero si sigo siempre los nodos visitados siempre se crea uno.
saludos
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej 2 semana 4

de Facundo Benavides -
así es
En respuesta a Facundo Benavides

Re: ej 2 semana 4

de Bruno Stefano Lombardo Palleiro -
Perfecto, pasé el  algoritmo en limpio con esos detalles, y me gustaría saber si las partes b y c están bien.
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej 2 semana 4

de Facundo Benavides -
en la parte b) si g es dag entonces devuelve un ot) faltaría mencionar los resultados del libro que intervienen en la demo y al final falta probar que "no quedan más nodos".
en la parte b) si tiene un ciclo lo devuelve) la primera oración es confusa y tautológica.
parte c) ok