El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios con Grafos

Siguiente ►
►

Toda la teoría del módulo está sobre la mesa: modelado (07-01), la clase Grafo (07-02), BFS/DFS/Kahn (07-03), Dijkstra y compañía (07-04), MST y Union-Find (07-05) y sus aplicaciones (07-06). Esta lección es íntegramente práctica: seis ejercicios progresivos, sin teoría nueva, alrededor de un proyecto real de TaskFlow — el lanzamiento de su app móvil. Intenta resolver cada uno por tu cuenta antes de mirar la solución; el orden importa, porque cada ejercicio reutiliza piezas del anterior. Necesitarás la clase Grafo y las funciones bfs, orden_topologico e invertir de las lecciones anteriores.

Contenido

  1. El proyecto de partida
  2. Ejercicio 1: construir y consultar el grafo del proyecto
  3. Ejercicio 2: el camino con menos pasos entre dos tareas
  4. Ejercicio 3: detectar y listar el ciclo de dependencias
  5. Ejercicio 4: orden de ejecución con desempate por prioridad
  6. Ejercicio 5: islas de tareas (proyectos independientes)
  7. Ejercicio 6: la rejilla como grafo implícito
  8. Soluciones

El proyecto de partida

El equipo planifica en TaskFlow el lanzamiento de la app móvil. Estas son las tareas (con su prioridad, 1 = máxima) y sus dependencias, en lenguaje natural:

Tarea Prioridad Depende de
definir_alcance 1 —
disenar_pantallas 2 definir_alcance
elegir_stack 1 definir_alcance
implementar_login 2 disenar_pantallas, elegir_stack
implementar_tablero 1 disenar_pantallas, elegir_stack
conectar_api 1 implementar_login, implementar_tablero
pruebas_usabilidad 2 conectar_api
preparar_marketing 3 —
publicar_tienda 1 pruebas_usabilidad, preparar_marketing 
graph LR
    A[definir_alcance] --> B[disenar_pantallas]
    A --> C[elegir_stack]
    B --> D[implementar_login]
    C --> D
    B --> E[implementar_tablero]
    C --> E
    D --> F[conectar_api]
    E --> F
    F --> G[pruebas_usabilidad]
    M[preparar_marketing] --> H
    G --> H[publicar_tienda]

Ejercicio 1: construir y consultar el grafo del proyecto

Construye el grafo movil con la clase Grafo (recuerda la convención del módulo: anadir_arista(A, B) = "B depende de A") y un diccionario prioridades con la prioridad de cada tarea. Después responde con código: (a) ¿qué tareas pueden empezar ya (grado de entrada 0)?; (b) ¿cuántas tareas desbloquea directamente elegir_stack y cuáles son?; (c) ¿es publicar_tienda la única tarea "final" (grado de salida 0)?

Ejercicio 2: el camino con menos pasos entre dos tareas

El jefe de proyecto pregunta: "¿cuál es la cadena de dependencias más corta que lleva de definir_alcance a publicar_tienda?". Escribe camino_minimo_pasos(grafo, origen, destino) que devuelva la lista de tareas del camino con menos aristas (o None si no hay camino). Pista: BFS guardando predecesores, y reconstrucción hacia atrás como en Dijkstra (07-04) — pero sin montículo: aquí no hay pesos.

Ejercicio 3: detectar y listar el ciclo de dependencias

Un usuario despistado añade dos dependencias nuevas: la retroalimentación de usuarios llega tras publicar (publicar_tienda → retro_usuarios) y, con las prisas, declara que el diseño de pantallas depende de esa retroalimentación (retro_usuarios → disenar_pantallas). El proyecto queda bloqueado. hay_ciclo (07-03) solo devuelve True; para un mensaje de error útil, TaskFlow necesita enseñar el ciclo. Escribe encontrar_ciclo(grafo) que devuelva la lista de vértices del ciclo (terminando en el vértice inicial repetido), o None si no hay. Pista: en el DFS blanco/gris/negro, mantén además la lista camino de vértices grises; al toparte con un gris, el ciclo es el tramo de camino desde ese vértice.

Ejercicio 4: orden de ejecución con desempate por prioridad

orden_topologico (Kahn) elige arbitrariamente entre las tareas disponibles. El equipo quiere algo mejor: entre las tareas ejecutables en cada momento, primero la de mayor prioridad (menor número; a igual prioridad, orden alfabético). Escribe orden_topologico_prioridad(grafo, prioridades) sustituyendo la deque de Kahn por el heapq del módulo 4 con tuplas (prioridad, id). Aplícalo al grafo movil (sin las aristas del ejercicio 3) y compara la posición de preparar_marketing con la que le daría una cola normal.

Ejercicio 5: islas de tareas (proyectos independientes)

Al grafo movil se le suman las tareas de otro frente de trabajo: redisenar_logo → actualizar_web y actualizar_web → nota_prensa, más una tarea suelta sin relaciones, renovar_dominio. Escribe islas_de_tareas(grafo) que devuelva las componentes conexas (ignorando el sentido de las flechas, como en 07-03) ordenadas de mayor a menor tamaño, y úsala para responder: ¿cuántos proyectos independientes conviven en el tablero y de qué tamaño?

Ejercicio 6: la rejilla como grafo implícito

La oficina de TaskFlow estrena un robot de reparto de paquetes que se mueve por un almacén cuadriculado: . es suelo libre, # una estantería, S la salida del robot y M la mesa de destino:

almacen = [
    "S.#.",
    ".#..",
    "....",
    "#.#M",
]

Calcula el mínimo número de movimientos (arriba/abajo/izquierda/derecha) de S a M con BFS... sin construir ningún objeto Grafo. La rejilla ya es un grafo: cada celda libre es un vértice y sus vecinos se calculan al vuelo mirando las cuatro casillas contiguas. Este patrón de grafo implícito es importantísimo: demuestra que BFS necesita saber "dame los vecinos de v", no una estructura concreta.

Soluciones

Solución 1

movil = Grafo(dirigido=True)
dependencias_movil = [
    ("definir_alcance", "disenar_pantallas"),
    ("definir_alcance", "elegir_stack"),
    ("disenar_pantallas", "implementar_login"),
    ("elegir_stack", "implementar_login"),
    ("disenar_pantallas", "implementar_tablero"),
    ("elegir_stack", "implementar_tablero"),
    ("implementar_login", "conectar_api"),
    ("implementar_tablero", "conectar_api"),
    ("conectar_api", "pruebas_usabilidad"),
    ("pruebas_usabilidad", "publicar_tienda"),
    ("preparar_marketing", "publicar_tienda"),
]
for origen, destino in dependencias_movil:
    movil.anadir_arista(origen, destino)

prioridades = {
    "definir_alcance": 1, "disenar_pantallas": 2, "elegir_stack": 1,
    "implementar_login": 2, "implementar_tablero": 1, "conectar_api": 1,
    "pruebas_usabilidad": 2, "preparar_marketing": 3, "publicar_tienda": 1,
}

# (a) grado de entrada 0: pueden empezar hoy
grados = movil.grados_entrada()
print([t for t, g in grados.items() if g == 0])
# ['definir_alcance', 'preparar_marketing']

# (b) desbloqueos directos de elegir_stack
print(movil.grado_salida("elegir_stack"), list(movil.vecinos("elegir_stack")))
# 2 ['implementar_login', 'implementar_tablero']

# (c) tareas finales: grado de salida 0
print([t for t in movil.vertices() if movil.grado_salida(t) == 0])
# ['publicar_tienda']  -> sí, es la única

Comentarios: todas las tareas aparecen en alguna arista, así que no hizo falta anadir_vertice explícito — pero revisa siempre esa suposición (aquí renovar_dominio del ejercicio 5 la romperá). Las respuestas salen de los métodos de la clase, sin ningún algoritmo: modelar bien ya responde preguntas.

Solución 2

from collections import deque

def camino_minimo_pasos(grafo, origen, destino):
    if origen == destino:
        return [origen]
    predecesor = {origen: None}          # hace tambien de visitados (07-03)
    cola = deque([origen])
    while cola:
        actual = cola.popleft()
        for vecino in grafo.vecinos(actual):
            if vecino not in predecesor:
                predecesor[vecino] = actual
                if vecino == destino:    # llegamos: podemos parar ya
                    camino = [destino]
                    while predecesor[camino[-1]] is not None:
                        camino.append(predecesor[camino[-1]])
                    return camino[::-1]  # se reconstruye del reves, como en 07-04
                cola.append(vecino)
    return None                          # cola vacia sin llegar: inalcanzable

print(camino_minimo_pasos(movil, "definir_alcance", "publicar_tienda"))
# ['definir_alcance', 'disenar_pantallas', 'implementar_login',
#  'conectar_api', 'pruebas_usabilidad', 'publicar_tienda']

Comentarios: el dict de predecesores cumple dos papeles (marcar visitados y recordar el camino), igual que en Dijkstra pero sin pesos ni montículo. Poder cortar en cuanto se alcanza el destino es un lujo exclusivo de BFS: la primera visita garantiza el mínimo de aristas. Hay dos caminos de 5 aristas (por login o por tablero); BFS devuelve el primero que descubre, y ambos son correctos.

Solución 3

def encontrar_ciclo(grafo):
    BLANCO, GRIS, NEGRO = 0, 1, 2
    color = {v: BLANCO for v in grafo.vertices()}
    camino = []                                  # los vertices grises, en orden

    def visitar(v):
        color[v] = GRIS
        camino.append(v)
        for vecino in grafo.vecinos(v):
            if color[vecino] == GRIS:            # arista hacia el camino actual
                inicio = camino.index(vecino)    # donde empieza el ciclo
                return camino[inicio:] + [vecino]
            if color[vecino] == BLANCO:
                ciclo = visitar(vecino)
                if ciclo:
                    return ciclo                 # propagar el hallazgo hacia arriba
        camino.pop()                             # backtracking: v deja el camino
        color[v] = NEGRO
        return None

    for v in grafo.vertices():
        if color[v] == BLANCO:
            ciclo = visitar(v)
            if ciclo:
                return ciclo
    return None

movil.anadir_arista("publicar_tienda", "retro_usuarios")
movil.anadir_arista("retro_usuarios", "disenar_pantallas")
print(encontrar_ciclo(movil))
# ['disenar_pantallas', 'implementar_login', 'conectar_api',
#  'pruebas_usabilidad', 'publicar_tienda', 'retro_usuarios', 'disenar_pantallas']

# limpiar para los siguientes ejercicios (eliminar_arista: ejercicio 2 de 07-02)
movil.eliminar_arista("publicar_tienda", "retro_usuarios")
movil.eliminar_arista("retro_usuarios", "disenar_pantallas")

Comentarios: la única novedad sobre hay_ciclo (07-03) es la lista camino, que crece al pintar de gris y encoge en el backtracking — una pila explícita, módulo 3, que retrata en todo momento la rama actual del DFS. Al toparse con un gris, el tramo desde su posición es exactamente el ciclo; se añade el vértice repetido al final para que el mensaje al usuario se lea como un círculo cerrado. Con esta lista, TaskFlow puede mostrar: "no puedo añadir la dependencia: disenar_pantallas → ... → retro_usuarios → disenar_pantallas".

Solución 4

import heapq

def orden_topologico_prioridad(grafo, prioridades):
    grados = grafo.grados_entrada()
    monticulo = [(prioridades[v], v) for v, g in grados.items() if g == 0]
    heapq.heapify(monticulo)
    orden = []
    while monticulo:
        _, actual = heapq.heappop(monticulo)     # la ejecutable mas prioritaria
        orden.append(actual)
        for vecino in grafo.vecinos(actual):
            grados[vecino] -= 1
            if grados[vecino] == 0:
                heapq.heappush(monticulo, (prioridades[vecino], vecino))
    if len(orden) < len(grados):
        raise ValueError("Hay un ciclo de dependencias")
    return orden

prioridades["retro_usuarios"] = 3        # quedo como vertice tras el ejercicio 3
print(orden_topologico_prioridad(movil, prioridades))
# ['definir_alcance', 'elegir_stack', 'disenar_pantallas', 'implementar_tablero',
#  'implementar_login', 'conectar_api', 'pruebas_usabilidad',
#  'preparar_marketing', 'publicar_tienda', 'retro_usuarios']

Comentarios: es Kahn letra por letra con la deque cambiada por un montículo — la misma sustitución cola→cola de prioridad que convirtió la Cola en BandejaUrgencias en el módulo 4. Las tuplas (prioridad, id) desempatan solas: primero por número, luego alfabéticamente, sin necesidad del contador del módulo 4 porque los ids son strings comparables. Fíjate en preparar_marketing: es ejecutable desde el minuto uno, pero su prioridad 3 la relega hasta el final (solo sale cuando es la única opción); una cola FIFO la habría ejecutado la segunda o tercera. El orden sigue siendo topológicamente válido: el montículo solo contiene tareas con todas sus dependencias cumplidas.

Solución 5

movil.anadir_arista("redisenar_logo", "actualizar_web")
movil.anadir_arista("actualizar_web", "nota_prensa")
movil.anadir_vertice("renovar_dominio")          # ¡sin aristas: alta explicita!

def islas_de_tareas(grafo):
    nd = Grafo(dirigido=False)                   # version sin sentido de flechas
    for v in grafo.vertices():
        nd.anadir_vertice(v)
        for destino in grafo.vecinos(v):
            nd.anadir_arista(v, destino)
    visitados, islas = set(), []
    for v in nd.vertices():
        if v not in visitados:
            isla = bfs(nd, v)                    # toda la componente de v
            visitados.update(isla)
            islas.append(isla)
    return sorted(islas, key=len, reverse=True)

for isla in islas_de_tareas(movil):
    print(len(isla), isla)
# 9 ['definir_alcance', ..., 'pruebas_usabilidad', 'publicar_tienda']
# 3 ['redisenar_logo', 'actualizar_web', 'nota_prensa']
# 1 ['retro_usuarios']
# 1 ['renovar_dominio']

Comentarios: cuatro islas — la app móvil (9 tareas), la campaña de imagen (3) y dos tareas sueltas. ¿Sorprende retro_usuarios? En el ejercicio 3 eliminamos sus dos aristas, pero el vértice siguió dado de alta: ahora aparece como isla propia, un recordatorio de que V y E son conjuntos independientes (07-01). Dos detalles más a vigilar: la conversión a no dirigido antes de buscar componentes (con las flechas, publicar_tienda no "vería" a preparar_marketing), y el alta explícita de renovar_dominio, que sin aristas no existiría en el grafo — el error clásico de 07-02. Alternativa perfectamente válida: UnionFind (07-05) uniendo los extremos de cada arista; las raíces finales son las islas.

Solución 6

from collections import deque

def pasos_minimos(rejilla):
    filas, columnas = len(rejilla), len(rejilla[0])
    for f in range(filas):                       # localizar S y M
        for c in range(columnas):
            if rejilla[f][c] == "S":
                salida = (f, c)
            elif rejilla[f][c] == "M":
                meta = (f, c)

    visitados = {salida}                         # el set de tuplas del modulo 5
    cola = deque([(salida, 0)])                  # (celda, pasos hasta ella)
    while cola:
        (f, c), pasos = cola.popleft()
        if (f, c) == meta:
            return pasos
        for df, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:   # las 4 direcciones
            nf, nc = f + df, c + dc
            if (0 <= nf < filas and 0 <= nc < columnas      # dentro del tablero
                    and rejilla[nf][nc] != "#"              # no es estanteria
                    and (nf, nc) not in visitados):
                visitados.add((nf, nc))                     # marcar al encolar
                cola.append(((nf, nc), pasos + 1))
    return None                                  # M inalcanzable

print(pasos_minimos(almacen))   # 6

Comentarios: es el bfs de 07-03 con dos cambios cosméticos: los vértices son tuplas (fila, columna) —hashables, por eso valen como elementos del set— y los "vecinos" no se leen de ninguna lista de adyacencia: se generan al vuelo sumando los cuatro desplazamientos y filtrando límites y muros. Un camino óptimo de 6 pasos: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (3,3); compruébalo dibujando sobre la rejilla. La lección de fondo: BFS no necesita la clase Grafo, solo una función de vecinos. Mapas de juegos, estados de un puzle, versiones de un documento: cualquier cosa con "estados y transiciones" es un grafo implícito y todo el módulo le aplica.

Errores Comunes y Consejos

  • Construir aristas con la convención invertida. Si escribes anadir_arista("disenar_pantallas", "definir_alcance") pensando "depende de", todos los algoritmos posteriores trabajarán sobre un proyecto del revés. Relee cada arista como "al terminar A se desbloquea B" antes de continuar.
  • Olvidar los vértices sin aristas (renovar_dominio): no aparecen en islas, órdenes ni recuentos. Alta explícita siempre.
  • camino.index(vecino) en grafos enormes es O(longitud del camino); para producción se guardaría también la posición de cada vértice gris en un dict. Para entender el algoritmo, la versión clara gana.
  • Probar solo el camino feliz. Ejecuta camino_minimo_pasos con destino inalcanzable, encontrar_ciclo sobre el grafo limpio y el almacén con la meta tapiada: la mitad de los errores reales viven en los None.
  • Consejo final del módulo: cuando un problema nuevo te desconcierte, pregúntate "¿qué son aquí los vértices y qué las aristas?". Es la pregunta que convierte robots en rejillas, tareas en DAGs y usuarios en redes — y una vez respondida, los algoritmos son siempre los mismos seis de este módulo.

Conclusión

Seis ejercicios y un proyecto entero después, los grafos han pasado de concepto a herramienta: has construido y consultado el grafo de un lanzamiento real, encontrado la cadena de dependencias más corta con BFS y predecesores, convertido "hay un ciclo" en un mensaje de error que enseña el ciclo, hecho que Kahn respete las prioridades con el montículo del módulo 4, separado el tablero en proyectos independientes y descubierto que hasta un almacén cuadriculado es un grafo si se le pregunta bien.

Y con esto, algo más grande: TaskFlow está completo en estructuras. Repasa lo construido a lo largo del curso — el tablero sobre arrays y listas enlazadas, el deshacer con pilas, las notificaciones y urgencias con colas y montículos, los índices instantáneos con tablas hash, las jerarquías con árboles y, desde este módulo, las dependencias, órdenes y rutas con grafos. No queda ninguna pieza fundamental por conocer. Lo que queda es criterio: ante un problema nuevo, ¿qué estructura eliges y por qué? Ese es exactamente el tema del módulo 8: mirar atrás con perspectiva, aprender a elegir estructura con argumentos de coste y de diseño, y rematar el curso con recursos para seguir y proyectos finales que integren todo lo aprendido.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados