Ordenação Topológica

Uma ordem topológica de um grafo direcionado posiciona toda aresta u → v com u antes de v. Essa ordem existe exatamente quando o grafo é acíclico.

Algoritmo de Kahn

1. Calcule o grau de entrada de cada vértice.
2. Enfileire todos os vértices com grau de entrada zero.
3. Remova um vértice, acrescente-o à ordem e decremente os graus de entrada dos vizinhos.
4. Enfileire os vizinhos cujo grau de entrada se tornar zero.
5. Se menos de V vértices forem emitidos, existe um ciclo direcionado.

static List<Integer> topologicalOrder(List<List<Integer>> graph) {
    int[] indegree = new int[graph.size()];
    for (List<Integer> edges : graph) {
        for (int target : edges) indegree[target]++;
    }
    Queue<Integer> ready = new ArrayDeque<>();
    for (int v = 0; v < indegree.length; v++) if (indegree[v] == 0) ready.add(v);

    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int vertex = ready.remove();
        order.add(vertex);
        for (int target : graph.get(vertex)) {
            if (--indegree[target] == 0) ready.add(target);
        }
    }
    if (order.size() != graph.size()) {
        throw new IllegalArgumentException("graph contains a directed cycle");
    }
    return order;
}

Cada vértice emitido não possui, naquele momento, nenhuma aresta de entrada proveniente dos vértices restantes; portanto, é seguro posicioná-lo em seguida. O algoritmo usa tempo Θ(V + E) e espaço auxiliar Θ(V). Em geral, as ordens não são únicas; uma fila de prioridade pode escolher o menor vértice disponível de forma canônica, ao custo adicional de fatores logarítmicos.