Practico 3, Ejercicio 1, Parte a

Re: Practico 3, Ejercicio 1, Parte a

de Alvaro Martin -
Número de respuestas: 3
La respuesta a algunas de esas preguntas requiere un algoritmo en sí misma. Por ejemplo, encontrar una arista (x,y) que está en G pero no en T podría implementarse recorriendo las aristas de G y verificando, para cada una, si está en T. Poder hacer esta verificación eficientemente requiere usar alguna estructura para representar T que lo habilite. Por ejemplo, si T se representa mediante un arreglo parent[] tal que para cada nodo u (representado como un índice de 1 a n) parent[u] nos da el padre de u en T, esa verificación se puede hacer en tiempo O(1) y la búsqueda de tal arista en tiempo O(m+n).

Para este problema en particular creo que es más sencillo resolver todo durante la recorrida DFS que hacerlo a posteriori a partir del árbol.

Saludos,
Álvaro
En respuesta a Alvaro Martin

Re: Practico 3, Ejercicio 1, Parte a

de Mateo Elisee Lengronne Gilles -
Buenas,
suponiendo que se tiene un algoritmo iterativo de DFS, usando una pila, cuando se hace la búsqueda en los nodos adyacentes al actual, como me podría fijar en ese momento si llegué a un punto donde estoy en presencia de un ciclo? O sea, si llego a un nodo adyacente ya explorado, para poder resolver en ese momento si hay un ciclo, cual tendría que ser la condición?
Por la propiedad 3.7 sabemos que si x-y pertenece a G y no a T, entonces uno es ancestro del otro.

Supongamos u es el nodo del top de la pila, que se toma al principio del while, luego dentro del for de adyacentes, se toma el nodo v(tal que exista arista u-v), si v no fue explorado, entonces se pone en la pila y se pone padre[v]=u, pero si ya fue explorado? No me queda claro ese momento, ni como encontrar el ciclo que contenga la arista que cumple la prop 3.7,
No sé si me expliqué bien, desde ya muchas gracias
En respuesta a Mateo Elisee Lengronne Gilles

Re: Practico 3, Ejercicio 1, Parte a

de Mateo Elisee Lengronne Gilles -
O sea, si v ya fue explorado y no es igual a padre[u], entonces estamos en presencia de un ciclo no? con esa arista u-v siendo la que cumple la propiedad 3.7, de ahí como sería el algoritmo para encontrar el ciclo?
En respuesta a Mateo Elisee Lengronne Gilles

Re: Practico 3, Ejercicio 1, Parte a

de Fernando Fernandez -
Hola Mateo.
Hay un par de cosas que no me quedan claras.
Mencionás un algoritmo iterativo. Pero no está del todo claro cómo es, porque en principio podría haber muchos algoritmos iterativos. ¿Es similar al de la página 93 del libro, manteniendo, como se explica más abajo, el padre de cada vértice?
También hacés referencia a la propiedad 3.7, que es de un algoritmo recursivo. ¿Cómo se relaciona con el iterativo? ¿Cuáles son los x e y?

Aún con estas dudas de cómo es el algoritmo, me parece que, si solo te interesa determinar si existe un ciclo (no mostrar uno de ellos), lo podés saber si padre[v] ya está definido y, como bien decís, no es padre[u].
En cambio, si querés mostrar el ciclo, v debe ser un vértice que, además de no ser padre[u], ya está explorado. Y el ciclo sería v, u, padre[u], padre[padre[u]], ..., v.