Un ordenamiento topológico coloca las tareas de un grafo dirigido en una secuencia que respeta todas sus dependencias: cada requisito aparece antes que aquello que depende de él.
Muchos problemas contienen actividades que no pueden realizarse en cualquier orden. Para compilar un programa se necesitan antes ciertos archivos; para cursar una materia pueden exigirse correlativas; para construir un producto algunas piezas deben estar terminadas previamente.
Estas relaciones se representan mediante un grafo dirigido. Una arista u → v indica que u debe aparecer antes que v. El ordenamiento topológico busca una secuencia lineal que respete todas esas restricciones.
Un orden topológico de un grafo dirigido G = (V, E) es una secuencia que contiene cada vértice exactamente una vez y cumple la siguiente condición:
Por ejemplo, si existen las dependencias A → C y B → C, tanto A como B deben estar antes que C. Sin embargo, la condición no determina necesariamente cuál debe aparecer primero entre A y B.
Un ordenamiento topológico existe si y solo si el grafo es un DAG, sigla de Directed Acyclic Graph: grafo dirigido acíclico.
Si A depende de B, B de C y C de A, ninguna tarea puede colocarse primero. El ciclo expresa dependencias incompatibles y hace imposible construir el orden.
Cuando dos vértices no están relacionados por una dependencia, pueden intercambiar sus posiciones sin invalidar el resultado.
| Dependencias | Órdenes posibles |
|---|---|
| A → C, B → C | A, B, C o B, A, C |
| A → B, B → C | Únicamente A, B, C |
Si en cada paso hay un único vértice disponible, el orden topológico es único. Si alguna vez podemos elegir entre dos o más, existen varios órdenes válidos.
El grado de entrada de un vértice es la cantidad de aristas que llegan a él. En un grafo de dependencias representa cuántos requisitos directos siguen pendientes.
Todo DAG posee al menos un vértice con grado de entrada cero. Si no existiera ninguno, al retroceder indefinidamente por las dependencias terminaríamos encontrando un ciclo.
Elige cualquiera de los vértices disponibles, es decir, aquellos cuyo grado de entrada actual es cero. Al seleccionar uno se eliminan sus aristas salientes y pueden habilitarse nuevas tareas.
Vértices disponibles
Orden construido
Acción
Los nodos verdes tienen grado de entrada cero y pueden elegirse. Los celestes ya fueron procesados. El botón para agregar un ciclo permite observar cómo Kahn detecta que el orden es imposible.
El algoritmo de Kahn elimina repetidamente vértices con grado de entrada cero:
La cola puede reemplazarse por una pila o una cola de prioridad. Cambiar la estructura modifica cuál de los posibles órdenes se obtiene, pero no la validez del algoritmo.
function ordenTopologico(grafo) {
const vertices = Object.keys(grafo);
const gradoEntrada = Object.fromEntries(
vertices.map(v => [v, 0])
);
for (const origen of vertices) {
for (const destino of grafo[origen]) {
gradoEntrada[destino]++;
}
}
const cola = vertices.filter(v => gradoEntrada[v] === 0);
const orden = [];
let frente = 0;
while (frente < cola.length) {
const actual = cola[frente++];
orden.push(actual);
for (const vecino of grafo[actual]) {
gradoEntrada[vecino]--;
if (gradoEntrada[vecino] === 0) cola.push(vecino);
}
}
return orden.length === vertices.length ? orden : null;
}La función devuelve null cuando no logra procesar todos los vértices, lo que indica la presencia de al menos un ciclo dirigido.
Si la cola queda vacía antes de procesar todos los vértices, los nodos restantes conservan dependencias entre ellos. No puede existir un orden topológico completo.
Kahn confirma que hay un ciclo, aunque por sí solo no devuelve necesariamente los vértices exactos que lo forman.
También se puede obtener un orden topológico con DFS. Un vértice se agrega al resultado después de terminar de explorar todos sus descendientes. Al final se invierte la lista de finalización.
Para detectar ciclos se utilizan tres estados: no visitado, en proceso y terminado. Encontrar una arista hacia un vértice en proceso revela un ciclo dirigido.
function ordenTopologicoDFS(grafo) {
const estado = {}; // 0: nuevo, 1: en proceso, 2: terminado
const resultado = [];
function visitar(actual) {
if (estado[actual] === 1) return false; // ciclo
if (estado[actual] === 2) return true;
estado[actual] = 1;
for (const vecino of grafo[actual]) {
if (!visitar(vecino)) return false;
}
estado[actual] = 2;
resultado.push(actual);
return true;
}
for (const vertice of Object.keys(grafo)) {
if (!estado[vertice] && !visitar(vertice)) return null;
}
return resultado.reverse();
}Para comprobar una secuencia se registra la posición de cada vértice. Después se verifica que el origen de cada arista aparezca antes que su destino.
function esOrdenValido(orden, aristas) {
const posicion = new Map(
orden.map((vertice, indice) => [vertice, indice])
);
return aristas.every(([origen, destino]) =>
posicion.has(origen) &&
posicion.has(destino) &&
posicion.get(origen) < posicion.get(destino)
);
}Además debe comprobarse que la secuencia incluya exactamente una vez todos los vértices del grafo.
| Característica | Kahn | DFS |
|---|---|---|
| Idea central | Eliminar grados de entrada cero | Ordenar por finalización |
| Estructura | Cola y contador de grados | Pila de recursión y estados |
| Detección de ciclo | Quedan vértices sin procesar | Arista hacia un nodo en proceso |
| Elección lexicográfica | Natural con cola de prioridad | Depende del orden de exploración |
Ambos métodos tienen la misma complejidad asintótica. Kahn suele resultar más intuitivo para planificar tareas disponibles; DFS se integra bien con otros análisis basados en profundidad.
Con listas de adyacencia, tanto Kahn como DFS visitan cada vértice y examinan cada arista una cantidad constante de veces.
Calcular repetidamente los grados desde cero produciría trabajo innecesario. Kahn es eficiente porque actualiza únicamente los vecinos del vértice recién procesado.
| Problema | Interpretación del orden |
|---|---|
| Compilación | Construir módulos después de sus dependencias |
| Plan de estudios | Cursar materias después de sus correlativas |
| Gestión de proyectos | Programar tareas respetando requisitos previos |
| Instalación de paquetes | Instalar bibliotecas antes de los programas que las usan |
| Hojas de cálculo | Recalcular celdas en un orden válido |
| Procesamiento de datos | Ejecutar etapas de una canalización según sus entradas |
El ordenamiento topológico determina una secuencia válida, pero no resuelve por sí solo cuestiones de duración, recursos limitados o ejecución paralela.
El ordenamiento topológico transforma dependencias parciales en una secuencia ejecutable. Los algoritmos de Kahn y DFS permiten construirla eficientemente y, al mismo tiempo, descubrir cuándo un ciclo vuelve incompatibles las restricciones.
En el próximo tema profundizaremos en la detección de ciclos para grafos dirigidos y no dirigidos.