Ordenamiento Topológico

¿Qué es un ordenamiento topológico?

Analogía: Piensa en las materias de una carrera universitaria. Algunas requieren prerrequisitos: no puedes tomar Cálculo 2 sin Cálculo 1. Un ordenamiento topológico es un orden válido para cursarlas todas respetando los prerrequisitos.

Formalmente: dado un grafo dirigido acíclico (DAG), encuentra un orden lineal de los nodos tal que si hay una arista $u \to v$, entonces $u$ aparece antes que $v$.

Algoritmo de Kahn (BFS)

Usa los grados de entrada (cuántas aristas llegan a cada nodo):

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int gradoEntrada[MAXN];

vector<int> topoSort(int n) {
    queue<int> q;
    vector<int> orden;

    // Agregar nodos con grado de entrada 0
    for (int i = 1; i <= n; i++) {
        if (gradoEntrada[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        orden.push_back(u);

        for (int v : adj[u]) {
            gradoEntrada[v]--;
            if (gradoEntrada[v] == 0) {
                q.push(v);
            }
        }
    }

    // Si no procesamos todos los nodos, hay ciclo
    if (orden.size() != n) {
        return {};  // Ciclo detectado
    }

    return orden;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        gradoEntrada[v]++;
    }

    vector<int> orden = topoSort(n);

    if (orden.empty()) {
        cout << "Hay ciclo, no existe ordenamiento topológico" << endl;
    } else {
        for (int x : orden) cout << x << " ";
        cout << endl;
    }

    return 0;
}

Algoritmo con DFS

vector<int> orden;
bool vis[MAXN];
bool enStack[MAXN];
bool hayCiclo = false;

void dfs(int u) {
    vis[u] = true;
    enStack[u] = true;

    for (int v : adj[u]) {
        if (enStack[v]) { hayCiclo = true; return; }
        if (!vis[v]) dfs(v);
        if (hayCiclo) return;
    }

    enStack[u] = false;
    orden.push_back(u);
}

// En main: hacer DFS desde todos los nodos, luego reverse(orden)

El ordenamiento topológico es el reverso del orden de finalización del DFS.

Ejercicio de práctica

Dadas N tareas y M dependencias (la tarea U debe hacerse antes que V), encuentra un orden válido para completar todas las tareas.

Ver solución

Usa el algoritmo de Kahn mostrado arriba. Si el resultado tiene menos de N elementos, hay dependencias circulares.