El Orden Topológico Explicado, con Código

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

¿Qué Es un Orden Topológico?

Un orden topológico es una ordenación lineal de los nodos de un grafo acíclico dirigido (DAG) tal que, para cada arista dirigida de u a v, el nodo u aparece antes que el nodo v. En pocas palabras: alinéalo todo para que cada flecha apunte hacia adelante.

Esa definición lleva dos condiciones incorporadas. El grafo debe ser dirigido (las dependencias tienen dirección: A antes de B no es lo mismo que B antes de A) y acíclico (sin ciclos). Si A debe ir antes que B y B debe ir antes que A, no puede existir un orden válido. Los árboles y los DAG son primos cercanos aquí; para el lado de los árboles, consulta árboles con raíz.

Cuándo lo Necesitas

El orden topológico es la respuesta siempre que un problema suene a "haz estas cosas en un orden que respete sus requisitos previos". Lo reconocerás por estas señales:

• Dependencias: "La tarea X requiere que la tarea Y esté terminada primero."
• Ordenar o planificar: "¿En qué orden puedo cursar estas asignaturas?"
• Compilar y construir: "Compilar los módulos para que cada import ya exista."
• Resolución: "Instalar paquetes para que cada dependencia se instale antes de lo que la necesita."

Es uno de los patrones más comunes en las entrevistas técnicas, por lo que aparece en la guía de algoritmos de grafos para entrevistas de programación y forma una etapa de la hoja de ruta de teoría de grafos.

El Algoritmo de Kahn, Paso a Paso

El método más intuitivo es el algoritmo de Kahn. Se apoya en un número por nodo: el grado de entrada, la cuenta de aristas entrantes. Un nodo con grado de entrada 0 no tiene requisitos pendientes, así que es seguro colocarlo a continuación.

El bucle es simple: toma cualquier nodo con grado de entrada 0, emítelo y elimina sus aristas salientes, lo que baja los grados de entrada de sus vecinos. Repite hasta que no quede nada. Ejecutémoslo en este DAG. Cada nodo lleva su posición en un orden válido.

Aquí está la traza. La cola contiene los nodos cuyo grado de entrada ha llegado a 0. Empezamos con A, el único nodo que no depende de nada.

Fíjate en que, tras tomar A, tanto B como C bajaron su grado de entrada a 0 a la vez. Cualquiera podría ir después, que es justo por qué un DAG suele tener muchos órdenes válidos. Ver caer los grados de entrada en un grafo en vivo lo hace encajar, lo que puedes probar en el visualizador de algoritmos.

Implementación en Python

El algoritmo de Kahn se traduce casi directamente a código. Calculamos cada grado de entrada, sembramos una cola con los nodos de grado de entrada cero y la vaciamos.

from collections import deque, defaultdict

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:          # la arista u -> v significa u antes que v
        graph[u].append(v)
        in_degree[v] += 1

    # Sembrar con cada nodo que no tiene requisitos previos.
    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1        # eliminar la arista
            if in_degree[neighbour] == 0:    # no quedan requisitos previos
                queue.append(neighbour)

    # Si algún nodo nunca llegó a grado de entrada 0, un ciclo lo bloqueó.
    if len(order) == num_nodes:
        return order
    return []   # ciclo detectado, sin orden válido

La comprobación final es la parte elegante: si a la salida le falta algún nodo, esos nodos están atrapados en un ciclo. Así que el mismo código que ordena un DAG también detecta si el grafo era siquiera un DAG.

El Enfoque DFS

Hay un segundo método clásico basado en la búsqueda en profundidad. Ejecuta DFS y, cuando un nodo termina (todos sus descendientes están explorados), apílalo. El orden topológico es la pila leída al revés.

La intuición: un nodo termina solo después de que todo lo que apunta haya terminado, así que en orden inverso de finalización cae antes que todos sus descendientes. La versión DFS no necesita llevar la cuenta de los grados de entrada, pero aún debes protegerte de los ciclos rastreando los nodos en el camino de recursión actual. Ambos enfoques son igual de válidos; el de Kahn suele ser más fácil de razonar, mientras que DFS es más compacto.

Los Ciclos y Por Qué lo Rompen

Un orden topológico existe si y solo si el grafo es acíclico. La razón es inmediata: un ciclo A → B → A exige que A vaya antes que B y B antes que A al mismo tiempo, lo cual es imposible en una línea.

La consecuencia útil: el orden topológico también es un detector de ciclos. En el algoritmo de Kahn, si no puedes emitir los V nodos, los nodos restantes forman al menos un ciclo. En la versión DFS, encontrar un nodo que ya está en tu camino actual señala un ciclo.

Por eso las preguntas de entrevista tipo "Course Schedule", que en realidad preguntan "¿es esto siquiera posible?", se resuelven con un orden topológico.

Complejidad

Ambos algoritmos son óptimos: tocan cada nodo y cada arista exactamente una vez.

Ese costo lineal es por qué el orden topológico escala a grafos de dependencias enormes. Para ver cómo se compara con todos los demás algoritmos de grafos, consulta la guía de complejidad y la chuleta de una página.

Aplicaciones en el Mundo Real

• Sistemas de compilación: Make, Bazel y compañía ordenan topológicamente los objetivos para que las dependencias se construyan primero.
• Gestores de paquetes: npm, pip y apt resuelven el orden de instalación a partir de un DAG de dependencias.
• Planificación de tareas y trabajos: hojas de cálculo recalculando celdas, pipelines de CI ordenando etapas, planificadores de cursos.
• Compiladores: ordenar declaraciones y evaluar expresiones para que cada símbolo esté definido antes de usarse.