Grafos AvanzadosgrafosDAGordenamiento-topológicodependencias

Ordenamiento Topológico

Aprende a ordenar tareas con dependencias usando ordenamiento topológico

OOI Oaxaca9 de febrero de 20265 min read

¿Qué es el ordenamiento topológico?

El ordenamiento topológico ordena los nodos de un DAG (Directed Acyclic Graph) de forma que para cada arista $u \to v$ , el nodo $u$ aparece antes que $v$ .

Grafo:
    1 → 2 → 4
    ↓   ↓   ↓
    3 → 5 → 6

Ordenamientos válidos:
- 1, 2, 3, 4, 5, 6
- 1, 2, 4, 3, 5, 6
- 1, 3, 2, 5, 4, 6

Aplicaciones

Compilación: Ordenar archivos según dependencias
Cursos: Prerequisitos de materias
Tareas: Scheduling con dependencias
Build systems: Makefile, npm install

Método 1: Kahn's Algorithm (BFS)

Usa grados de entrada y una cola:

#include <bits/stdc++.h>
using namespace std;

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

vector<int> topSortKahn(int n) {
    queue<int> cola;
    vector<int> orden;

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

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

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

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

    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 = topSortKahn(n);

    if (orden.empty()) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        for (int x : orden) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

Método 2: DFS

Agrega nodos al terminar de procesar:

vector<int> adj[MAXN];
bool visitado[MAXN];
bool enStack[MAXN];
vector<int> orden;
bool hayCiclo;

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

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfs(v);
        } else if (enStack[v]) {
            hayCiclo = true;  // Detectamos ciclo
        }
    }

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

vector<int> topSortDFS(int n) {
    fill(visitado, visitado + n + 1, false);
    fill(enStack, enStack + n + 1, false);
    orden.clear();
    hayCiclo = false;

    for (int i = 1; i <= n; i++) {
        if (!visitado[i]) {
            dfs(i);
        }
    }

    if (hayCiclo) {
        return {};
    }

    reverse(orden.begin(), orden.end());
    return orden;
}

Ordenamiento topológico lexicográficamente menor

Usa priority_queue en vez de queue:

vector<int> topSortLex(int n) {
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> orden;

    for (int i = 1; i <= n; i++) {
        if (gradoEntrada[i] == 0) {
            pq.push(i);
        }
    }

    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        orden.push_back(u);

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

    return orden.size() == n ? orden : vector<int>();
}

Contar ordenamientos topológicos

Usando DP con bitmask (para n pequeño):

int dp[1 << 20];
int adj_mask[20];  // adj_mask[i] = máscara de nodos a los que i apunta

int contarOrdenamientos(int n) {
    // Precalcular máscaras de adyacencia
    for (int u = 0; u < n; u++) {
        adj_mask[u] = 0;
        for (int v : adj[u]) {
            adj_mask[u] |= (1 << v);
        }
    }

    dp[0] = 1;
    int full = (1 << n) - 1;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == 0) continue;

        for (int u = 0; u < n; u++) {
            if (mask & (1 << u)) continue;  // Ya usado

            // Verificar que todas las dependencias de u están en mask
            if ((adj_mask[u] & mask) == adj_mask[u]) {
                dp[mask | (1 << u)] += dp[mask];
            }
        }
    }

    return dp[full];
}

Camino más largo en DAG

Usando orden topológico:

int dist[MAXN];

int caminoMasLargo(int n) {
    vector<int> orden = topSortKahn(n);

    fill(dist, dist + n + 1, 0);

    for (int u : orden) {
        for (int v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + 1);
        }
    }

    return *max_element(dist + 1, dist + n + 1);
}

Template completo

#include <bits/stdc++.h>
using namespace std;

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

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

    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

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

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

    return order.size() == n ? order : vector<int>();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        inDegree[b]++;
    }

    vector<int> result = topoSort(n);

    if (result.empty()) {
        cout << "IMPOSSIBLE\n";
    } else {
        for (int x : result) {
            cout << x << " ";
        }
        cout << "\n";
    }

    return 0;
}