Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 27/32

Qué va primero: orden topológico

✕
1/8

Dependencias como flechas

Un plan de estudios inventado: Programación I (P1) antes de Programación II (P2); P2 antes de Estructuras de datos (ED); ED y Matemáticas discretas (MD) antes de Algoritmos (AL); y AL antes de Compiladores (CO). Cada «antes de» es una flecha.

Un orden topológico es una fila de todos los vértices donde cada flecha apunta hacia adelante: nadie aparece antes que algo de lo que depende. Sólo existe si el grafo es dirigido y sin ciclos, un DAG (*directed acyclic graph*). Si A necesita a B y B necesita a A, no hay por dónde empezar.

Y casi nunca es único: MD puede ir al principio o justo antes de AL.

P1P2EDMDALCO
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • Los dos primeros órdenes son válidos aunque son distintos: MD puede ir en varios lugares.
  • El tercero no: pone Algoritmos antes que Estructuras de datos y que Discretas.
Toda la lección en una página

Dependencias como flechas

Un plan de estudios inventado: Programación I (P1) antes de Programación II (P2); P2 antes de Estructuras de datos (ED); ED y Matemáticas discretas (MD) antes de Algoritmos (AL); y AL antes de Compiladores (CO). Cada «antes de» es una flecha.

Un orden topológico es una fila de todos los vértices donde cada flecha apunta hacia adelante: nadie aparece antes que algo de lo que depende. Sólo existe si el grafo es dirigido y sin ciclos, un DAG (*directed acyclic graph*). Si A necesita a B y B necesita a A, no hay por dónde empezar.

Y casi nunca es único: MD puede ir al principio o justo antes de AL.

P1P2EDMDALCO
const requisitos = [["P1", "P2"], ["P2", "ED"], ["ED", "AL"], ["MD", "AL"], ["AL", "CO"]];

function esValido(orden) {
  const pos = {};
  orden.forEach((m, i) => { pos[m] = i; });
  // cada flecha "antes -> después" tiene que apuntar hacia adelante
  return requisitos.every(([antes, despues]) => pos[antes] < pos[despues]);
}

console.log(esValido(["P1", "MD", "P2", "ED", "AL", "CO"]));
console.log(esValido(["MD", "P1", "P2", "ED", "AL", "CO"]));
console.log(esValido(["P1", "P2", "AL", "ED", "MD", "CO"]));
  • Los dos primeros órdenes son válidos aunque son distintos: MD puede ir en varios lugares.
  • El tercero no: pone Algoritmos antes que Estructuras de datos y que Discretas.

El algoritmo de Kahn

La forma más clara de armarlo es contar el grado de entrada de cada vértice: cuántas flechas le llegan, o sea, cuántas cosas le faltan.

  • Los de grado 0 no dependen de nada: van a una cola.
  • Se saca uno, se anota en el orden y se le resta 1 a cada vértice al que apunta (ya se cumplió ese requisito).
  • Al que llegue a 0 se le forma en la cola.

Si al final el orden tiene menos vértices que el grafo, los que faltan están atorados en un ciclo: nunca llegaron a 0. Cuesta O(V + E).

const grafo = {
  P1: ["P2"],
  P2: ["ED"],
  ED: ["AL"],
  MD: ["AL"],
  AL: ["CO"],
  CO: [],
};

function kahn(grafo) {
  const grado = {};
  for (const v in grafo) grado[v] = 0;
  for (const v in grafo) for (const w of grafo[v]) grado[w]++;
  console.log("grados de entrada:", grado);

  const cola = Object.keys(grafo).filter((v) => grado[v] === 0);
  const orden = [];
  let cabeza = 0;
  while (cabeza < cola.length) {
    const v = cola[cabeza++];
    orden.push(v);
    for (const w of grafo[v]) {
      grado[w]--;                      // un requisito menos
      if (grado[w] === 0) cola.push(w);
    }
  }
  // si faltan vértices, quedaron atorados en un ciclo
  return orden.length === Object.keys(grafo).length ? orden : null;
}

console.log(kahn(grafo));
console.log(kahn({ A: ["B"], B: ["C"], C: ["A"] }));
  • P1 y MD empiezan con grado 0; AL empieza con 2 (le faltan ED y MD).
  • Sale [P1, MD, P2, ED, AL, CO]: AL sólo entra a la cola cuando ED y MD ya salieron.
  • En el triángulo A → B → C → A nadie empieza en 0: devuelve null. (Los grados salen dos veces porque kahn se llama dos veces.)

Con DFS, y para qué se usa

Otra forma: un DFS que anota cada vértice al terminar con todo lo que depende de él. Esa lista, al revés, es un orden topológico. Da otro orden igual de válido (para detectar ciclos así hay que distinguir «visitando» de «terminado», que aquí se omite).

Esto está en más lugares de los que parece: npm decide en qué orden instalar paquetes, make en qué orden compilar archivos, una hoja de cálculo en qué orden recalcular celdas que dependen de otras, y una receta en qué orden hacer los pasos.

const grafo = {
  P1: ["P2"],
  P2: ["ED"],
  ED: ["AL"],
  MD: ["AL"],
  AL: ["CO"],
  CO: [],
};

function topoDFS(grafo) {
  const visto = new Set(), salida = [];
  function visitar(v) {
    if (visto.has(v)) return;
    visto.add(v);
    for (const w of grafo[v]) visitar(w);
    salida.push(v);   // termina después de todo lo que depende de él
  }
  for (const v in grafo) visitar(v);
  console.log("al terminar:", salida);
  return salida.reverse();
}

console.log(topoDFS(grafo));
  • Al terminar sale CO primero (nada depende de él) y P1 casi al final.
  • Al revés queda [MD, P1, P2, ED, AL, CO]: distinto al de Kahn y también válido.