Ordenación topológica con DFS en postorden

El segundo algoritmo clásico de ordenamiento topológico utiliza DFS con procesamiento en postorden. Después de explorar por completo todos los vecinos de un nodo (y sus descendientes), inserte el nodo en una pila. Cuando se hayan procesado todos los nodos, extraiga los elementos de la pila para obtener el orden topológico. Que un nodo se inserte en la pila después de todas sus dependencias significa que aparece primero en el orden, por lo que el postorden invertido es el ordenamiento topológico.

Considere un grafo de dependencias en el que el curso A requiere el curso B. Cuando DFS visita A, primero recurre en B. B no tiene prerrequisitos, por lo que termina primero y se inserta primero en la pila. Después termina A y se inserta en la pila. Al extraer la pila, se obtiene A antes que B en la salida, pero al final invertimos el resultado y obtenemos B antes que A: tome primero B y después A. El postorden inserta las dependencias antes que los elementos dependientes, por lo que la pila invertida es un orden topológico válido.

Utilice tres estados para los nodos visitados: WHITE (0) = sin visitar, GREY (1) = en proceso (en la pila de llamadas de DFS), BLACK (2) = procesado por completo. Una arista de retroceso —una arista hacia un nodo GREY— indica que existe un ciclo. Las aristas hacia nodos BLACK son seguras, ya que esos nodos ya se exploraron por completo. Este esquema de tres colores detecta correctamente todos los ciclos en grafos dirigidos.

Utilice un DFS recursivo que coloree los nodos, los inserte en una pila en postorden y devuelva False al detectar un ciclo. Después de visitar todos los nodos, la pila invertida proporciona el orden topológico.

El límite de recursión de Python (1000 de forma predeterminada) puede ser un problema en grafos grandes. Un DFS iterativo que utilice una pila explícita evita este problema. El truco consiste en insertar inicialmente (node, False); al extraerlo con False, inserte (node, True) (lo que significa «volveré aquí después de explorar») y, después, inserte todos los vecinos no visitados con False. Al extraerlo con True, coloréelo de BLACK e insértelo en la pila de resultados.

Ambos algoritmos se ejecutan en O(V + E). Diferencias principales: Kahn (BFS) produce naturalmente los nodos en un orden que prioriza las dependencias más tempranas y ofrece una detección de ciclos más sencilla (mediante la comprobación de la longitud). El postorden de DFS funciona de forma recursiva y detecta explícitamente las aristas de retroceso. Se prefiere Kahn cuando se desea el resultado en orden directo, sin invertirlo. Se prefiere DFS cuando se necesita el postorden completo para otros fines, como la detección de SCC. Ambos métodos son aceptables en entrevistas.

En un árbol, el postorden visita el subárbol izquierdo → el subárbol derecho → la raíz. En un DAG, el DFS en postorden visita todas las dependencias de un nodo antes de procesar el propio nodo: es la misma idea generalizada a múltiples predecesores y a una estructura de grafo arbitraria. La raíz de un árbol de DFS (el nodo inicial) se inserta después que todos sus descendientes, por lo que aparece primero en la pila invertida: la posición topológica correcta para un nodo sin predecesores.

Alien Dictionary: dada una lista ordenada de palabras de un idioma alienígena, deduzca el orden de sus caracteres. Compare las palabras adyacentes carácter por carácter para encontrar la primera diferencia; esto proporciona una arista c1 → c2, que significa que c1 aparece antes que c2. Reúna todas esas aristas y ejecute un ordenamiento topológico para obtener el orden de los caracteres alienígenas. Si existe un ciclo, el orden no es válido.

Algunos problemas solicitan un ordenamiento topológico que cumpla restricciones adicionales, como mantener el orden relativo de los elementos de la lista original. Combine el algoritmo de Kahn con una cola de prioridad personalizada o con un ordenamiento previo: conserve el orden relativo original mediante un ordenamiento estable del contenido de la cola en cada paso. Estas variantes con restricciones ponen a prueba una comprensión más profunda de la flexibilidad del algoritmo.

Algunas frases indicadoras en problemas de entrevistas que apuntan al ordenamiento topológico son: «dadas las dependencias», «prerrequisitos», «orden de las tareas», «orden de compilación», «¿se pueden completar todas las tareas?», «encuentre una secuencia válida». Si el problema implica ordenar elementos de modo que algunos deban aparecer antes que otros, construya un grafo dirigido y aplique el ordenamiento topológico de Kahn o de DFS. La detección de ciclos suele ser un requisito adicional del mismo problema.

DFS y Kahn pueden producir órdenes topológicos válidos diferentes para el mismo grafo. Ambos son correctos: un DAG puede tener varios órdenes topológicos válidos. Para verificar la corrección, compruebe que, para cada arista u → v del grafo, u aparezca antes que v en el orden de salida. En problemas de entrevistas que exigen un orden específico (por ejemplo, el lexicográficamente menor), utilice Kahn con un montículo mínimo; el postorden de DFS no produce naturalmente el orden lexicográficamente menor.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió que: el ordenamiento topológico mediante el postorden de DFS inserta los nodos después de explorar todas sus dependencias, el marcado con tres colores (WHITE/GREY/BLACK) detecta ciclos mediante aristas de retroceso hacia nodos GREY y al invertir la pila del postorden se obtiene un orden topológico válido. A continuación aplicaremos directamente el ordenamiento topológico a los problemas Course Schedule I y II.