El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

Cerramos el módulo anterior con una confesión: todos nuestros árboles escondían un supuesto silencioso, el de que cada nodo tiene un solo padre. En cuanto una tarea de TaskFlow depende de varias a la vez —"desplegar API" necesita que terminen tanto "migrar BD" como "configurar servidor"— la jerarquía se queda corta. Y si además alguien crea una dependencia circular por error, el árbol directamente no puede representarlo. La estructura que sí puede con todo esto es el grafo: la más general del curso, la que engloba a listas y árboles como casos particulares, y la que modela redes sociales, mapas, la web o las dependencias de un proyecto. En esta lección aprenderemos su vocabulario; todavía sin código de representación (eso llega en la siguiente lección) ni algoritmos (que esperan en la 07-03 con el visitados prometido en el módulo 5).

Contenido

Del árbol al grafo: por qué necesitamos algo más general
Definición formal: vértices y aristas
Terminología esencial (con diagramas)
El árbol como caso particular de grafo
Modelar las dependencias de TaskFlow como grafo dirigido
Grafos en el mundo real

Del árbol al grafo: por qué necesitamos algo más general

Recordemos las dos limitaciones concretas con las que tropezamos al final del módulo 6:

Varios padres: en un árbol, "desplegar API" solo podría colgar de "migrar BD" o de "configurar servidor", nunca de ambas. Pero en un proyecto real depende de las dos.
Ciclos posibles: nada impide que un usuario de TaskFlow declare que A depende de B, B de C y C de A. Un árbol no puede ni expresarlo; un grafo sí, y además nos dará algoritmos para detectarlo y avisar al usuario.

Un grafo elimina ambas restricciones: cualquier nodo puede conectarse con cualquier otro, en cualquier dirección, incluso formando ciclos. A cambio, perdemos las garantías cómodas del árbol (raíz única, ausencia de ciclos, un solo camino entre dos nodos), y por eso los algoritmos sobre grafos tendrán que ser más cuidadosos. Ese es el precio de la generalidad.

Definición formal: vértices y aristas

Un grafo es un par G = (V, E) donde:

V es un conjunto de vértices (también llamados nodos): las entidades. En TaskFlow, las tareas.
E es un conjunto de aristas (edges): las relaciones entre pares de vértices. En TaskFlow, las dependencias.

Por ejemplo, con tres tareas:

V = { migrar_bd, configurar_servidor, desplegar_api }
E = { (migrar_bd, desplegar_api), (configurar_servidor, desplegar_api) }

Fíjate en que aquí las aristas son pares ordenados: (migrar_bd, desplegar_api) no es lo mismo que (desplegar_api, migrar_bd). Eso nos lleva directamente a la terminología.

Terminología esencial (con diagramas)

Dirigido y no dirigido

En un grafo dirigido (o digrafo), cada arista tiene sentido: va de un origen a un destino y se dibuja con flecha. "Migrar BD desbloquea desplegar API" no es simétrico.
En un grafo no dirigido, la arista es mutua: si A está conectada con B, B lo está con A. "Ana y Bea son amigas".

graph LR
    subgraph Dirigido
        A[migrar_bd] --> B[desplegar_api]
    end
    subgraph No dirigido
        C[Ana] --- D[Bea]
    end

Ponderado y no ponderado

Un grafo es ponderado cuando cada arista lleva asociado un número (su peso): coste, distancia, horas... En TaskFlow, el peso de una arista podrá ser las horas que cuesta completar la transición entre dos tareas. Si solo nos importa si hay conexión, el grafo es no ponderado.

graph LR
    A[disenar_esquema] -->|3 h| B[migrar_bd]
    B -->|2 h| C[desplegar_api]

Grado de un vértice

El grado mide cuántas aristas tocan un vértice. En grafos dirigidos se divide en dos:

Concepto	Definición	Lectura en TaskFlow
Grado de entrada	Aristas que llegan al vértice	Cuántas tareas debe esperar esta tarea
Grado de salida	Aristas que salen del vértice	Cuántas tareas desbloquea al terminar
Grado (no dirigido)	Aristas incidentes	Número de conexiones

En el diagrama de "desplegar API": grado de entrada 2 (espera a dos tareas), grado de salida lo que desbloquee después.

Camino y ciclo

Un camino es una secuencia de vértices conectados por aristas consecutivas: disenar_esquema → migrar_bd → desplegar_api. Su longitud es su número de aristas (2 en el ejemplo).
Un ciclo es un camino que empieza y termina en el mismo vértice sin repetir aristas. En un grafo de dependencias, un ciclo es un error fatal: nadie puede empezar.

graph LR
    A[disenar_ui] --> B[implementar_ui]
    B --> C[revisar_doc]
    C --> A
    style A fill:#fdd,stroke:#c00
    style B fill:#fdd,stroke:#c00
    style C fill:#fdd,stroke:#c00

Este ciclo (disenar_ui → implementar_ui → revisar_doc → disenar_ui) significa que ninguna de las tres tareas puede arrancar jamás. ¿Te suena "detección de ciclos"? En el módulo 2 detectamos ciclos en listas enlazadas con el algoritmo de Floyd; en grafos necesitaremos una técnica distinta (lección 07-03), pero el problema es hermano.

Conexo y componentes conexas

Un grafo no dirigido es conexo si desde cualquier vértice se puede llegar a cualquier otro. Si no, se divide en componentes conexas: "islas" de vértices conectados entre sí pero aisladas del resto. En TaskFlow, dos componentes son dos proyectos que no comparten ninguna dependencia.

graph LR
    subgraph Componente 1
        A[tarea_a] --- B[tarea_b] --- C[tarea_c]
    end
    subgraph Componente 2
        D[tarea_d] --- E[tarea_e]
    end

Denso y disperso

Un grafo denso tiene muchas aristas: cerca del máximo posible, que con n vértices dirigidos es n · (n - 1).
Un grafo disperso (sparse) tiene pocas: del orden de n.

Los grafos de dependencias reales son casi siempre dispersos (cada tarea depende de 1–3 tareas, no de las 200 del proyecto). Este detalle, que parece menor, decidirá en la próxima lección cómo conviene representar el grafo en memoria.

DAG: grafo dirigido acíclico

Un DAG (Directed Acyclic Graph) es un grafo dirigido sin ciclos. Es la estrella de este módulo: un proyecto de TaskFlow bien formado es exactamente un DAG. Permite varios padres (a diferencia del árbol) pero prohíbe los círculos viciosos (a diferencia del grafo general).

graph LR
    A[disenar_esquema] --> B[migrar_bd]
    S[configurar_servidor] --> C
    B --> C[desplegar_api]
    C --> D[pruebas_integracion]
    U[disenar_ui] --> I[implementar_ui]
    I --> D
    D --> L[lanzamiento]

Observa: "desplegar_api" y "pruebas_integracion" tienen varios padres (imposible en un árbol) y aun así no hay ningún ciclo. Este DAG será el ejemplo recurrente de todo el módulo.

El árbol como caso particular de grafo

Ahora podemos colocar el módulo 6 en el mapa: un árbol es un grafo conexo y acíclico (y en su versión con raíz, dirigido con grado de entrada 1 en todos los vértices salvo la raíz, que tiene 0). Toda la jerarquía de estructuras del curso encaja:

Estructura	Como grafo
Lista enlazada (módulo 2)	Grafo dirigido donde cada vértice tiene grado de salida ≤ 1: un camino
Lista circular (módulo 2)	Un ciclo simple
Árbol (módulo 6)	Grafo conexo acíclico; con raíz: cada nodo, un solo padre
DAG	Dirigido sin ciclos; se permiten varios padres
Grafo general	Sin restricciones

Cada fila relaja una restricción de la anterior. Los algoritmos que veremos funcionan sobre grafos generales y, por tanto, también sobre todos los casos particulares: BFS sobre un árbol es exactamente el recorrido por niveles del módulo 6.

Modelar las dependencias de TaskFlow como grafo dirigido

Nos falta fijar un detalle que arrastraremos todo el módulo: el sentido de las flechas. Hay dos convenciones posibles y ambas son legítimas; lo importante es elegir una y no mezclarlas.

Opción A: A → B significa "A depende de B".
Opción B: A → B significa "B depende de A" (A debe terminar antes; la flecha apunta a lo que A desbloquea).

En este curso adoptamos la opción B: la arista migrar_bd → desplegar_api se lee "al terminar migrar_bd se acerca el desbloqueo de desplegar_api". Es la convención natural para los algoritmos que vienen: seguir las flechas es avanzar en el tiempo del proyecto, y el "orden válido de ejecución" saldrá de recorrerlas hacia delante.

Con esta convención, y recordando que cada tarea de TaskFlow sigue siendo el dict de siempre (id, titulo, prioridad, estado, asignada_a, etiquetas, horas), el modelo mental completo es:

Vértice: el id de una tarea (el dict completo vivirá aparte, en un diccionario id → tarea, como en el índice del módulo 5).
Arista A → B: B depende de A.
Grado de entrada de B: número de dependencias pendientes de B. Cuando llegue a 0... B es ejecutable. Guarda esta idea: es la semilla del orden topológico (07-03).
Peso de la arista (cuando lo haya): horas o coste de la transición (07-04).

Grafos en el mundo real

El mismo vocabulario modela sistemas muy distintos; solo cambia qué es vértice y qué es arista:

Sistema	Vértices	Aristas	¿Dirigido?	¿Ponderado?
Red social	Personas	Amistad / "seguir a"	Amistad no; "seguir" sí	Normalmente no
Mapa de carreteras	Cruces, ciudades	Tramos de vía	A veces (sentido único)	Sí (km, minutos)
La web	Páginas	Enlaces	Sí	No (o relevancia)
Paquetes de software (`pip`)	Paquetes	"requiere"	Sí	No
TaskFlow	Tareas	Dependencias	Sí	Opcional (horas)

Fíjate en que pip install resuelve exactamente el mismo problema que TaskFlow: dado un DAG de dependencias, encontrar un orden válido de instalación y quejarse si hay ciclos. Cuando en 07-03 implementemos el orden topológico, habrás entendido cómo funciona por dentro un gestor de paquetes.

Errores Comunes y Consejos

Mezclar las dos convenciones de flecha. Si un día dibujas A → B como "A depende de B" y otro como "B depende de A", tus algoritmos darán resultados invertidos. Fija la convención por escrito (nosotros: la flecha apunta a lo que se desbloquea) y sé consecuente.
Confundir camino con arista. Que exista un camino de A a C no significa que exista la arista directa A → C. Son preguntas distintas y, como veremos, con costes de cálculo muy distintos.
Asumir que todo grafo dirigido es un DAG. La ausencia de ciclos hay que comprobarla, no suponerla; los datos reales (introducidos por usuarios) traen ciclos por error con más frecuencia de la que imaginas.
Olvidar los vértices aislados. Una tarea sin ninguna dependencia (ni entrante ni saliente) sigue siendo un vértice del grafo. Los conjuntos V y E son independientes: puede haber vértices sin aristas.
Consejo: antes de programar nada, dibuja el grafo (mermaid o papel). En grafos, un buen dibujo evita la mitad de los errores de modelado.

Ejercicios

Ejercicio 1: clasificar grafos

Para cada sistema, indica si su grafo natural es dirigido o no dirigido, ponderado o no, y si esperas que sea un DAG: (a) el historial de "hecho a partir de" entre versiones de un documento; (b) vuelos comerciales entre aeropuertos con su duración; (c) enchufes conectados por cables en una oficina.

Ejercicio 2: leer un grafo de dependencias

Con la convención del curso (A → B = B depende de A) y el DAG de TaskFlow de esta lección, responde: (a) ¿grado de entrada y de salida de pruebas_integracion? (b) ¿qué tareas pueden empezar el primer día (sin esperar a nadie)? (c) escribe un camino de disenar_esquema a lanzamiento y su longitud.

Ejercicio 3: provocar un ciclo

Partiendo del mismo DAG, añade una sola arista que cree un ciclo, y explica con la lectura "depende de" por qué el proyecto resultante es imposible de ejecutar.

Soluciones

Solución 1:

(a) Dirigido (la relación "derivado de" tiene sentido), no ponderado, y es un DAG: una versión no puede derivar de una versión futura de sí misma.
(b) Dirigido (ida y vuelta pueden diferir o no existir), ponderado (duración), y no es un DAG: los ciclos (Madrid → París → Madrid) no solo existen sino que son deseables.
(c) No dirigido (el cable conecta en ambos sentidos), ponderado si nos importa la longitud del cable; "DAG" no aplica a grafos no dirigidos.

Solución 2:

(a) Entrada 2 (desplegar_api e implementar_ui llegan a ella), salida 1 (lanzamiento).
(b) Las de grado de entrada 0: disenar_esquema, configurar_servidor y disenar_ui.
(c) disenar_esquema → migrar_bd → desplegar_api → pruebas_integracion → lanzamiento, longitud 4 (cuatro aristas, cinco vértices).

Solución 3: Por ejemplo lanzamiento → disenar_esquema. Lectura: "disenar_esquema depende de lanzamiento". Pero lanzamiento depende (transitivamente) de disenar_esquema, así que cada una espera a la otra a través de la cadena: ninguna tarea del ciclo alcanza jamás grado de entrada 0 y el proyecto entero queda bloqueado. Cualquier arista "hacia atrás" sobre un camino existente vale como respuesta.

Conclusión

Ya hablamos el idioma de los grafos: vértices y aristas; dirigido, ponderado, grados, caminos, ciclos, componentes, denso frente a disperso, y el DAG como retrato fiel de un proyecto bien formado. Hemos situado listas y árboles como grafos con restricciones, y hemos fijado la convención que gobernará todo el módulo: la flecha apunta a la tarea que se desbloquea. Lo que aún no sabemos es cómo guardar un grafo en memoria: ¿una gran tabla de "quién conecta con quién" o un diccionario de vecinos? La respuesta —matriz de adyacencia frente a lista de adyacencia, con sus costes y su clase Grafo reutilizable— es exactamente el tema de la próxima lección.

Introducción a los Grafos