Inicio · Parte 04 — Matemática discreta para computación
algoritmo de Kahn: repetir «tomar vértice de grado de entrada 0»
si quedan vértices sin ordenar ⟹ hay cicloUn orden topológico es una ordenación lineal de los vértices tal que toda arista va de un vértice anterior a uno posterior. Existe si y solo si el grafo es acíclico, y esa equivalencia convierte el algoritmo en un detector de ciclos: si al terminar quedan vértices sin ordenar, esos vértices forman —o dependen de— al menos un ciclo.
El algoritmo de Kahn es directo: se toman repetidamente los vértices con grado de entrada cero (los que no dependen de nada pendiente), se emiten y se decrementan los grados de sus sucesores. Coste O(V + E), el mismo que BFS.
Este algoritmo es el que ejecuta todo sistema de construcción —make, Bazel, un DAG de Airflow— para decidir en qué orden ejecutar tareas. El mensaje «dependencia circular detectada» que emiten esos sistemas es literalmente el caso en que Kahn no consigue ordenar todos los nodos.
Y aquí está la conexión que da sentido a esta clase dentro del programa: la autodiferenciación en modo reverso recorre el grafo de cómputo en orden topológico inverso. La clase 306 lo hace explícito, y la clase 179 lo implementa: backward() construye el orden topológico y luego lo recorre al revés propagando gradientes. Sin esta clase, esa implementación parecería magia.
Orden topológico del pipeline y detección de ciclo.
Grafo (DAG):
entrada → limpieza → {features, split} → entrenamiento → evaluacion
Grados de entrada iniciales:
entrada 0, limpieza 1, features 1, split 1,
entrenamiento 2, evaluacion 1
Orden de Kahn:
entrada, limpieza, features, split, entrenamiento, evaluacion
6 de 6 vértices ordenados → es un DAG ✓
Con una arista extra evaluacion → limpieza:
ningún vértice queda con grado 0 tras entrada
vértices ordenados: 1 de 6
→ hay un ciclo, y los 5 restantes están dentro o dependen de élOrden topológico y detección de ciclos por conteo de Kahn.
python classes/part-04-matematica-discreta-para-computacion/096-dag-y-orden-topologico/lab.py
compmath run 096grafoorden_topologicoes_DAGnodos_ordenadosdiagnostico_si_fallauso{
"grafo": {
"entrada": [
"limpieza"
],
"limpieza": [
"features",
"split"
],
"features": [
"entrenamiento"
],
"split": [
"entrenamiento"
],
"entrenamiento": [
"evaluacion"
],
"evaluacion": []
},
"orden_topologico": [
"entrada",
"limpieza",
"features",
"split",
"entrenamiento",
"evaluacion"
],
"es_DAG": true,
"nodos_ordenados": 6,
"diagnostico_si_falla": "los nodos ausentes forman al menos un ciclo",
"uso": "planificación de tareas, build systems y grafos de cómputo"
}Sistemas de construcción, planificadores de tareas, resolución de dependencias de paquetes, evaluación de hojas de cálculo y autodiferenciación en modo reverso.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
10.1145/368996.369025 verificado en Crossref (2026-08-19).