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
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