Ejercicio 1, Práctico 3

Ejercicio 1, Práctico 3

de Nicolas Estefan Vidal -
Número de respuestas: 5

Hola, conseguí escribir un algoritmo para detectar ciclos en un grafo y devolver alguno de ellos. Creo que el algoritmo es correcto, pero se me está dificultando la parte de demostrar su corrección. Me podrían tirar algún pique y comentarme si el algoritmo va por buen camino? Esto es lo que escribí:

Muchas gracias, saludos!

En respuesta a Nicolas Estefan Vidal

Re: Ejercicio 1, Práctico 3

de Alvaro Martin -

Hola.

Creo que el algoritmo no es correcto. Por ejemplo, si el grafo solo tiene dos vértices conectados por una arista entiendo que este algoritmo reporta incorrectamente que hay un ciclo. Tampoco se tiene en cuenta que el grafo podría no ser conexo.

Como sugerencia, me parece que el algoritmo es más complicado de lo necesario y eso dificulta analizar su corrección. Esencialmente lo que hay que hacer es detectar una arista del grafo que no pertenece al árbol, y construir un ciclo desde ahí. El resultado (3.7) del libro y su demostración les podría ayudar.

Tengo la impresión de que la versión recursiva de DFS es más sencilla de adaptar a este problema que la iterativa, pero se puede hacer de cualquiera de las dos formas.

Saludos,
Álvaro

En respuesta a Alvaro Martin

Re: Ejercicio 1, Práctico 3

de Nicolas Estefan Vidal -
Muchas gracias por tu respuesta. Lo volví a intentar, teniendo en cuenta tus correcciones y llegué a un algoritmo. Me da la impresión de que se puede escribir más compacto haciendo uso de la recursión para devolver el ciclo, pero no me doy cuenta cómo. Podrías decirme si el algoritmo es correcto, y de no ser correcto, tirarme algún tip para corregirlo?
Esto es lo que escribí:
En respuesta a Nicolas Estefan Vidal

Re: Ejercicio 1, Práctico 3

de Nicolas Estefan Vidal -
En el and del elseif, la segunda condición debería ser parent[u] != v
En respuesta a Nicolas Estefan Vidal

Re: Ejercicio 1, Práctico 3

de Facundo Benavides -
hola Nicolás, mucho mejor. veo que levantaste varios de los señalamientos que había hecho Álvaro.
queda pendiente aún el hecho que G puede no ser conexo y por tanto, mientras no se encuentre ciclo hay que analizar cada una de las componentes conexas de G.
saludos