Buenas, como están? Me ayudarían en saber si esta justificación sobre tiempo para este algoritmo del ejercicio 2 del practico 4 es correcta o tiene fallas? En caso de estar mal, que puntos debería mejorar?. Saludos.
hola luciano,
la justificación es correcta en gral sin embargo anoto algunos detalles "no menores" en la última parte (construcción del ciclo)
- no vi que justificaras el paso donde se crea S' (no es trivial).
- la elección de un nodo v no es trivial ya que las aristas incidentes a iter pueden llevarme fuera de S'. ergo, podría tener que probar varios vs por cada iter hasta elegir uno que sirva.
- para implementar el camino (que contendrá necesariamente un ciclo) alcanza con una lista simple o una pila. observar que como estas estructuras invierten el orden entonces el ciclo (que es lo último que proceso en el while) queda al comienzo. luego la impresión del mismo se hace a partir del primero de la pila/lista hasta encontrar iter.
salvo eso, estaría bien de bien.
luego, a modo de discutir alternativas. cuando creas la lista de adyacencias entrantes ya podrías calcular el grado cargando un arreglo indeg que utilizás en el primer for. también se podría definir un contador de nodos con grado in mayor a cero. este serviría para no tener que recorrer orden para chequear su largo. o análogamente, la lista orden podría tener un cabezal donde se almacene la cantidad de elementos. por último, para crear S' alcanzaría con recorrer indeg tomando los que sean mayores que 0.
saludos
la justificación es correcta en gral sin embargo anoto algunos detalles "no menores" en la última parte (construcción del ciclo)
- no vi que justificaras el paso donde se crea S' (no es trivial).
- la elección de un nodo v no es trivial ya que las aristas incidentes a iter pueden llevarme fuera de S'. ergo, podría tener que probar varios vs por cada iter hasta elegir uno que sirva.
- para implementar el camino (que contendrá necesariamente un ciclo) alcanza con una lista simple o una pila. observar que como estas estructuras invierten el orden entonces el ciclo (que es lo último que proceso en el while) queda al comienzo. luego la impresión del mismo se hace a partir del primero de la pila/lista hasta encontrar iter.
salvo eso, estaría bien de bien.
luego, a modo de discutir alternativas. cuando creas la lista de adyacencias entrantes ya podrías calcular el grado cargando un arreglo indeg que utilizás en el primer for. también se podría definir un contador de nodos con grado in mayor a cero. este serviría para no tener que recorrer orden para chequear su largo. o análogamente, la lista orden podría tener un cabezal donde se almacene la cantidad de elementos. por último, para crear S' alcanzaría con recorrer indeg tomando los que sean mayores que 0.
saludos
Buenas,
Queria saber si mi pseudo algoritmo está bien.
Gracias
Queria saber si mi pseudo algoritmo está bien.
Gracias
solucion(s)
inicializar conjunto S vacio
inicializar arreglo indeg de largo #V
for each u in V
indeg[u] <- #aristas entrantes de u
if (indeg[u] = 0) agregar u a S
Inicializar lista L vacia
while (S no es vacio) {
remover un nodo i de S y de V y agregarlo a L
por cada nodo j con una arista i->j
indeg[j] --
if (indeg[j] = 0) agregar j a S
if (V es vacio)
devolver el orden topologico L
else //todos los nodos en V tienen aristas entrantes
crearListaAdyacenciasEntrantes(V)
Inicializar pila P vacia
Inicilizar arreglo de booleanos Visitado de largo #V en falso para todos
tomar un nodo i cualquiera de V y agregarlo a P
while (Visitado[i] es falso)
Visitado[i] <- verdadero
i <- primer nodo en la lista de adyacencias de aristas entrantes de i
agregar i a P
inicializar lista C vacia
ultimo <- pop(P)
agregar ultimo a C
while (top(P) != ultimo)
i <- pop(P)
agregar i a C
devolver C
crearListaAdyacenciasEntrantes(V)
por cada nodo v in V
por cada arista v->u
agregar v a la lista de adyacencias entrantes de u
hola amalia,
viene muy bien rumbeado. un detalle que tal vez quedó medio oculto. es el peligro que corremos con los pseudocódigos =D
cuando decís de eliminar i de V en el primer while, tendría cuidado. esa operación sobre una implementación de grafo basada en lista de adyacencias (salientes) no sería aconsejable antes de realizar el for de la sentencia que sigue porque justamente necesitamos recorrer la lista de adyacentes del nodo i.
saludos
viene muy bien rumbeado. un detalle que tal vez quedó medio oculto. es el peligro que corremos con los pseudocódigos =D
cuando decís de eliminar i de V en el primer while, tendría cuidado. esa operación sobre una implementación de grafo basada en lista de adyacencias (salientes) no sería aconsejable antes de realizar el for de la sentencia que sigue porque justamente necesitamos recorrer la lista de adyacentes del nodo i.
saludos
Gracias por la respuesta! En este caso, alcanzaría con dar vuelta el orden de esas dos sentencias no?
De otra manera podría no borrar los nodos de V, y cambiarían un par de cosas mas adelante: en lugar preguntar si V es vacío, preguntaría si #L es igual a #V, y en el else tendría que crear un conjunto auxiliar con los nodos que tienen indegree mayor a cero al terminar el primer while, lo que haría recorriendo el arreglo indeg.
De otra manera podría no borrar los nodos de V, y cambiarían un par de cosas mas adelante: en lugar preguntar si V es vacío, preguntaría si #L es igual a #V, y en el else tendría que crear un conjunto auxiliar con los nodos que tienen indegree mayor a cero al terminar el primer while, lo que haría recorriendo el arreglo indeg.
hola,
correcto.
correcto.