Ordenação Topológica

O problema, e a condição para ele ter solução

Você tem um conjunto de coisas e um conjunto de restrições da forma "A precisa vir antes de B". Uma ordenação topológica é uma sequência de todos os elementos em que toda aresta aponta para frente.

Modele como grafo dirigido: cada tarefa é um vértice, e A → B quer dizer "A precisa acontecer antes de B".

Aí aparece a condição, e ela é o coração do tópico: existe ordenação topológica se, e somente se, o grafo não tem ciclo. Um grafo dirigido sem ciclo tem um nome próprio, DAG (directed acyclic graph), e é o que você vai ver em todo enunciado.

A razão é intuitiva. Se A depende de B e B depende de A, quem vai primeiro? Nenhum dos dois pode, e não existe ordem. É o deadlock de dependências que todo mundo já viu num package.json ou num build quebrado.

Kahn: remover quem não depende de ninguém

O algoritmo de Kahn é o mais fácil de explicar para um humano, porque é o que você faria à mão.

Para cada vértice, conte quantas arestas chegam nele. Esse número é o grau de entrada, e ele quer dizer "quantos pré-requisitos ainda faltam".

1. Todo vértice com grau de entrada 0 pode ser feito agora. Ponha todos numa fila.
2. Tire um da fila e coloque na resposta.
3. Para cada vizinho dele, diminua o grau de entrada em 1. Se algum chegar a zero, ele foi liberado: entra na fila.
4. Repita.

from collections import deque

def kahn(vertices, adj):
    grau = {v: 0 for v in vertices}
    for u in vertices:
        for v in adj[u]:
            grau[v] += 1

    fila = deque(v for v in vertices if grau[v] == 0)
    ordem = []
    while fila:
        u = fila.popleft()
        ordem.append(u)
        for v in adj[u]:
            grau[v] -= 1
            if grau[v] == 0:
                fila.append(v)

    if len(ordem) < len(vertices):
        raise ValueError("ciclo: não existe ordenação")
    return ordem

Acompanhe o grau de entrada dentro de cada vértice no desenho. Ele é o estado que faz o algoritmo funcionar, e vê-lo cair até zero é ver a dependência sendo cumprida. Repare também no preset "muita coisa independente": a fila fica com vários vértices ao mesmo tempo, e cada um deles poderia sair primeiro.

A detecção de ciclo vem de graça

Rode o terceiro preset. A fila esvazia com só 4 dos 7 vértices na resposta, e o algoritmo para.

O que sobrou não é aleatório: os vértices que ficaram têm grau de entrada maior que zero e ninguém mais para zerá-lo, porque todos os que poderiam já saíram. A única forma disso acontecer é eles dependerem uns dos outros. O que sobra é o ciclo.

Isso dá o teste mais limpo de ciclo em grafo dirigido:

if len(ordem) < len(vertices):
    # existe ciclo, e ele está entre os vértices que faltaram

É por isso que o problema Course Schedule ("dá para terminar todas as matérias?") é resolvido com ordenação topológica: a resposta é sim exatamente quando a ordem sai completa.

A outra saída: DFS com pós-ordem

Existe uma segunda implementação, e ela é mais curta:

def topo_dfs(vertices, adj):
    visitado = set()
    ordem = []

    def dfs(u):
        visitado.add(u)
        for v in adj[u]:
            if v not in visitado:
                dfs(v)
        ordem.append(u)          # PÓS-ordem: depois de todos os descendentes

    for u in vertices:
        if u not in visitado:
            dfs(u)
    return ordem[::-1]           # inverte no fim

A ideia: em pós-ordem, um vértice só é anotado depois de todos os vértices alcançáveis a partir dele. Ou seja, ele é anotado depois de todos que dependem dele. Invertendo a lista, cada vértice aparece antes de todos os seus dependentes, que é a definição de ordenação topológica.

Os dois custam O(V + E): você toca em cada vértice e em cada aresta uma vez.

Um bônus do Kahn: quantos passos em paralelo

Como o Kahn libera vértices em camadas, ele responde de graça uma pergunta que o DFS não responde: quantas rodadas seriam necessárias se você pudesse executar em paralelo tudo que está liberado ao mesmo tempo?

Basta processar a fila em blocos, como no BFS por níveis:

rodadas = 0
while fila:
    for _ in range(len(fila)):        # trava o nível atual
        u = fila.popleft()
        ...
    rodadas += 1

Esse número é o caminho crítico do seu grafo de dependências, e é exatamente a conta que um sistema de build faz para saber o mínimo de tempo possível, mesmo com paralelismo infinito. É também o que responde problemas do tipo "quantos semestres no mínimo para terminar o curso".

Onde isso já está rodando

• Sistemas de build: make, Bazel, Gradle e o pipeline do seu CI ordenam alvos topologicamente. O "circular dependency detected" que você já viu é exatamente o len(ordem) < len(vertices).
• Gerenciadores de pacote: npm, pip e apt resolvem a ordem de instalação assim, e o "dependency cycle" é o mesmo erro.
• Migrations de banco: rodar na ordem em que as tabelas dependem umas das outras.
• Planilhas: o Excel recalcula células em ordem topológica das fórmulas, e o aviso de "referência circular" é a detecção de ciclo.
• Compiladores: ordem de inicialização de módulos e de avaliação de expressões.

Como praticar

Course Schedule é o "existe ordem?" e é o melhor primeiro problema, porque ele reduz a ordenação topológica a um sim ou não. Logo depois, Course Schedule II pede a ordem em si, e é o mesmo código devolvendo ordem em vez de um booleano.

Minimum Height Trees é uma variação bonita: você remove folhas em camadas, exatamente como o Kahn remove vértices de grau zero, até sobrar o centro do grafo. Ver que é o mesmo padrão com outra roupa vale mais que o problema em si.

Alien Dictionary é o passo mais difícil: você recebe palavras numa ordem desconhecida e precisa descobrir as arestas antes de ordenar. É o exercício definitivo de "enxergar o grafo", que a introdução a grafos levanta.

Uma dica de leitura de enunciado: as palavras "pré-requisito", "depende de", "antes de", "ordem de execução" e "circular" são o gatilho. Quando aparecerem, desenhe o grafo dirigido e pergunte se ele tem ciclo. Daí em diante o código é o desta página.

Depois daqui, a Árvore Geradora Mínima muda a pergunta de "em que ordem" para "quais arestas manter", e é o último algoritmo clássico deste grupo.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:41:07.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.