buenas, me estoy frustrando con la demostracion del ejercicio, podrian tirar algun pique por donde es o como seria? logre hacer esta segun mi algoritmo pero no me termina de convencer
hola natasha,
comienzo con el alg, porque tiene detalles a corregir y esto sería previo a probar su correctitud.
1, en la función DFS(G), me parece que alcanzaría con inicializar todo el array explored en false y ejecutar el while (prescindiendo del if).
2, la función bool hay_ciclo(G,s,explored):
2.1, entiendo que es recursiva y por tanto en la línea 5 debería invocarse a si misma (en lugar de DFS(s), que no estaría definida.
2.2, el alg no resuelve el problema porque el mismo motivo señaldo por álvaro en una consulta previa. si lo corrés con un G que tenga 2 vértices y una sola arista, devolvería que hay ciclo, cuando no lo hay. el problema está en el else de la línea que debería ser un elseif (evitado considerar vértices explorados inmediatamente antes). recomiendo revisar la propiedad 3.7 de K&T.
saludos
comienzo con el alg, porque tiene detalles a corregir y esto sería previo a probar su correctitud.
1, en la función DFS(G), me parece que alcanzaría con inicializar todo el array explored en false y ejecutar el while (prescindiendo del if).
2, la función bool hay_ciclo(G,s,explored):
2.1, entiendo que es recursiva y por tanto en la línea 5 debería invocarse a si misma (en lugar de DFS(s), que no estaría definida.
2.2, el alg no resuelve el problema porque el mismo motivo señaldo por álvaro en una consulta previa. si lo corrés con un G que tenga 2 vértices y una sola arista, devolvería que hay ciclo, cuando no lo hay. el problema está en el else de la línea que debería ser un elseif (evitado considerar vértices explorados inmediatamente antes). recomiendo revisar la propiedad 3.7 de K&T.
saludos
Lo único que no me quedo claro es como seria el elseif
hola,
digamos que el alg que necesito se divide entre hacer dfs (explorar el grafo en profundidad mientras no encuentro un ciclo), encontrar un ciclo y no hacer nada (no procesar ese nodo, simplemente pasar al siguiente adyacente).
en este sentido el if nos estaría resolviendo lo primero, el elseif lo segundo y al omitir un else estamos resolviendo lo tercero.
luego, al ingresar al else if, sabemos 2 cosas: que no se cumple la condición del if anterior (!explorado[v]) y que cumple la condición presente. entonces debemos pensar que condición extra imponer al nodo 'v' que ya fue explorado para que sea el nodo que cierra un ciclo.
como lo tenías (con un else) estabas considerando los casos de cierre de ciclo pero también otros que no correspondían (los padres fueron explorados pero NO cierran ciclos). el if que debemos agregar al else tiene por objetivo evitar esos casos que no queremos incluir y no debieran ser procesados (como menciono en este msj al comienzo).
espero haber aclarado un poco.
saludos
digamos que el alg que necesito se divide entre hacer dfs (explorar el grafo en profundidad mientras no encuentro un ciclo), encontrar un ciclo y no hacer nada (no procesar ese nodo, simplemente pasar al siguiente adyacente).
en este sentido el if nos estaría resolviendo lo primero, el elseif lo segundo y al omitir un else estamos resolviendo lo tercero.
luego, al ingresar al else if, sabemos 2 cosas: que no se cumple la condición del if anterior (!explorado[v]) y que cumple la condición presente. entonces debemos pensar que condición extra imponer al nodo 'v' que ya fue explorado para que sea el nodo que cierra un ciclo.
como lo tenías (con un else) estabas considerando los casos de cierre de ciclo pero también otros que no correspondían (los padres fueron explorados pero NO cierran ciclos). el if que debemos agregar al else tiene por objetivo evitar esos casos que no queremos incluir y no debieran ser procesados (como menciono en este msj al comienzo).
espero haber aclarado un poco.
saludos