Orden topológico (Kahn)

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 18 de la Ruta de Aprendizaje.

Qué problema resuelve

Un grafo dirigido puede expresar dependencias: u → v significa que hay que completar u antes que v. Un orden topológico coloca todos los vértices en una lista respetando cada dependencia. Existe si y solo si el grafo no tiene ciclos dirigidos; a ese grafo se le llama DAG.

Por ejemplo, con 0 → 2, 1 → 2 y 2 → 3, son válidos tanto 0,1,2,3 como 1,0,2,3. No necesitamos que exista una arista entre posiciones consecutivas de la lista: el orden topológico no es un camino.

La idea: elegir una tarea disponible

El grado de entrada de un vértice cuenta cuántas aristas llegan a él. Inicialmente, un vértice con grado de entrada cero no depende de ninguno: puede salir primero.

Guardamos los disponibles en una cola. Al retirar u, sus aristas dejan de representar tareas pendientes, así que restamos 1 al grado de entrada de cada destino. Si alguno llega a cero, queda disponible.

Paso del ejemploCola antes de extraerExtraídoNuevo disponible
10, 10ninguno; 2 aún depende de 1
2112
3223
433ninguno

Por qué funciona: cada vértice sale solo después de que salieron todos sus predecesores. Por tanto, toda arista apunta hacia una posición posterior del orden construido.

Si quedan vértices pero ninguno tiene grado de entrada cero, cada uno tiene un predecesor pendiente. Seguir esos predecesores en un conjunto finito obliga a repetir un vértice: hay un ciclo. Esto también explica por qué una dependencia circular impide completar el orden.

Implementación recomendada (C++)

vector<int> toposort(const vector<vector<int>>& g) {
    int n = g.size();
    vector<int> indeg(n, 0), order;
    for (int u = 0; u < n; u++) for (int v : g[u]) indeg[v]++;
    queue<int> q;
    for (int u = 0; u < n; u++) if (!indeg[u]) q.push(u);
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
    }
    return (int)order.size() == n ? order : vector<int>{};  // vacío = hay ciclo
}

La entrada es una lista de adyacencia dirigida, con vértices entre 0 y n-1. Se incluyen los vértices aislados. El vector vacío señala un ciclo cuando n > 0; para un grafo de cero vértices, el orden vacío es válido. Si tu aplicación distingue ambos casos, compara order.size() con n antes de devolver el resultado.

Costo: O(n+m) tiempo y O(n) memoria adicional. Cada vértice entra en la cola una vez y cada arista decrementa un contador una vez. Varias aristas iguales funcionan porque se cuentan y se descuentan por separado.

Qué cambia según el problema

La cola devuelve algún orden válido. Si piden el menor orden lexicográfico, sustituye la cola por una cola de prioridad que extraiga el menor disponible. Eso aumenta el costo a O(m+n log n).

Para propagar una DP sobre un DAG, procesa sus estados en este orden: cuando llega el turno de un vértice, sus predecesores ya están resueltos. Obtener el orden no decide por sí solo cuál es la transición de esa DP.

Para comprobarlo

Agrega 3 → 1 al ejemplo. Se puede retirar 0, pero luego la cola se vacía y quedan 1, 2 y 3. Identifica el ciclo y explica por qué devolver solo [0] no sería una respuesta válida.