Ordenação topológica por pós-ordem de DFS

O segundo algoritmo clássico de ordenação topológica usa DFS com processamento em pós-ordem. Depois de explorar completamente todos os vizinhos de um nó (e seus descendentes), coloque o nó em uma pilha. Quando todos os nós forem processados, retire os elementos da pilha para ler a ordem topológica. Um nó colocado na pilha depois de todas as suas dependências significa que ele vem primeiro na ordem — portanto, a pós-ordem invertida é a ordenação topológica.

Considere um grafo de dependências em que o curso A exige o curso B. Quando o DFS visita A, primeiro ele faz uma chamada recursiva para B. B não tem pré-requisitos, então termina primeiro e é colocado primeiro na pilha. Em seguida, A termina e é colocado na pilha. Retirar os elementos da pilha fornece A antes de B na saída — mas invertemos no final, obtendo B antes de A: faça B primeiro e depois A. A pós-ordem coloca as dependências antes dos elementos dependentes, portanto, a pilha invertida é uma ordem topológica válida.

Use três estados para os nós visitados: WHITE (0) = não visitado, GREY (1) = sendo processado no momento (na pilha de chamadas do DFS), BLACK (2) = totalmente processado. Uma aresta de retorno — uma aresta para um nó GREY — indica um ciclo. As arestas para nós BLACK são seguras (eles já foram explorados completamente). Esse esquema de três cores detecta corretamente todos os ciclos em grafos direcionados.

Use um DFS recursivo que atribua cores aos nós, coloque-os em uma pilha em pós-ordem e retorne o valor falso ao detectar um ciclo. Depois de visitar todos os nós, a pilha (invertida) fornece a ordem topológica.

O limite de recursão do Python (1000 por padrão) é uma preocupação para grafos grandes. Um DFS iterativo que usa uma pilha explícita evita esse problema. A técnica é: coloque inicialmente (node, False); quando ele for retirado com False, coloque (node, True) (o que significa “voltarei aqui depois de explorar”) e coloque todos os vizinhos não visitados com o valor falso. Quando for retirado com True, atribua BLACK a ele e coloque-o na pilha de resultados.

Ambos executam em O(V + E). Principais diferenças: o algoritmo de Kahn (BFS) produz naturalmente os nós em uma ordem que prioriza primeiro as dependências e tem uma detecção de ciclos mais simples (verificação do tamanho). A pós-ordem do DFS funciona recursivamente e detecta arestas de retorno explicitamente. O algoritmo de Kahn é preferível quando se deseja o resultado na ordem direta, sem inversão. O DFS é preferível quando se precisa da pós-ordem completa para outras finalidades (como detecção de SCC). Ambos são aceitáveis em entrevistas.

Em uma árvore, a pós-ordem visita a subárvore esquerda → a subárvore direita → a raiz. Em um DAG, o DFS em pós-ordem visita todas as dependências de um nó antes de processar o próprio nó — a mesma ideia generalizada para vários predecessores e uma estrutura de grafo arbitrária. A raiz de uma árvore de DFS (o nó inicial) é colocada por último entre seus descendentes, fazendo com que apareça primeiro na pilha invertida — a posição topológica correta para um nó sem predecessores.

Dicionário alienígena: dada uma lista ordenada de palavras em um idioma alienígena, determine a ordenação dos caracteres. Compare palavras adjacentes caractere por caractere para encontrar a primeira diferença — isso fornece uma aresta c1 → c2, significando que c1 vem antes de c2. Colete todas essas arestas e execute uma ordenação topológica para produzir a ordenação dos caracteres alienígenas. Se existir um ciclo, a ordenação será inválida.

Alguns problemas pedem uma ordenação topológica que satisfaça restrições adicionais, como manter a ordem relativa dos elementos da lista original. Combine o algoritmo de Kahn com uma fila de prioridade personalizada ou uma pré-ordenação: mantenha os elementos na ordem relativa original usando uma ordenação estável no conteúdo da fila a cada etapa. Essas variantes com restrições testam uma compreensão mais profunda da flexibilidade do algoritmo.

Frases indicativas em problemas de entrevistas que apontam para uma ordenação topológica: “dadas as dependências”, “pré-requisitos”, “ordenação de tarefas”, “ordem de construção”, “é possível concluir todas as tarefas?”, “encontre uma sequência válida”. Se o problema envolver uma ordenação de itens em que alguns devem vir antes de outros, construa um grafo direcionado e aplique o algoritmo de Kahn ou a ordenação topológica com DFS. A detecção de ciclos costuma ser um requisito secundário no mesmo problema.

DFS e Kahn podem produzir ordens topológicas válidas diferentes para o mesmo grafo. Ambas estão corretas — um DAG pode ter várias ordenações topológicas válidas. Para verificar a correção, confira se, para cada aresta u → v no grafo, u aparece antes de v na ordem de saída. Para problemas de entrevistas que exigem uma ordem específica (por exemplo, a ordem lexicograficamente menor), use o algoritmo de Kahn com uma fila de prioridade mínima — a pós-ordem do DFS não produz naturalmente a ordem lexicograficamente menor.

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para entrevistas de programação desta lição.

Nesta lição, você aprendeu: a ordenação topológica em pós-ordem com DFS coloca os nós depois que todas as suas dependências são exploradas, a marcação com três cores (WHITE/GREY/BLACK) detecta ciclos por meio de arestas de retorno para nós GREY e inverter a pilha de pós-ordem fornece uma ordenação topológica válida. A seguir, aplicaremos a ordenação topológica diretamente aos problemas Cronograma de cursos I e II.