Calculadora de Ordenação Topológica

Calculadora de Ordenação Topológica

A Calculadora de Ordenação Topológica computa uma ordenação linear dos vértices de um grafo acíclico direcionado (DAG) tal que cada aresta direcionada de u para v coloca u antes de v. Insira seu grafo como uma lista de arestas ou lista de adjacência e a ferramenta retornará a ordem topológica usando o algoritmo de Kahn ou DFS pós-ordem, detectará ciclos (com o caminho exato do ciclo), agrupará tarefas em camadas de execução paralela, contará o número de ordenações válidas e animará cada passo em um grafo interativo.

O que é uma ordenação topológica?

Dado um grafo direcionado G = (V, E), uma ordenação topológica (ou arranjo topológico) é um arranjo linear v₁, v₂, …, vₙ de seus vértices tal que para cada aresta direcionada (u → v), u aparece antes de v no arranjo. Uma ordenação topológica existe se e somente se o grafo não possui ciclos direcionados — ou seja, se o grafo for um DAG. A ordenação raramente é única: um grafo pode ter muitas ordenações topológicas válidas quando vários vértices têm grau de entrada zero ao mesmo tempo.

Algoritmos usados por esta calculadora

Algoritmo de Kahn (baseado em BFS, 1962)

O algoritmo de Kahn é a ordenação topológica mais intuitiva. Em cada etapa, ele escolhe um vértice com grau de entrada zero (sem arestas de entrada), anexa-o à saída e o "remove" do grafo, decrementando o grau de entrada de cada um de seus sucessores. Quando vários vértices têm grau de entrada zero, o desempate pode usar uma min-heap (fornecendo a menor ordenação lexicográfica) ou uma fila FIFO (fornecendo a ordem de inserção). O algoritmo de Kahn roda em tempo O(|V| + |E|) e funciona também como um detector de ciclos: se algum vértice ainda tiver grau de entrada > 0 após a fila esvaziar, o grafo possui um ciclo.

DFS pós-ordem (Tarjan, 1976)

O algoritmo DFS executa uma busca em profundidade e, sempre que um vértice termina (ou seja, todos os seus sucessores foram totalmente explorados), ele é empilhado. Inverter a pilha ao final resulta em uma ordem topológica válida. A detecção de ciclo é natural: encontrar um vértice que ainda está em progresso (marcado como CINZA) significa que uma aresta de retorno foi encontrada, portanto o grafo não é um DAG. O DFS pós-ordem também roda em tempo O(|V| + |E|).

Camadas de execução paralela

Uma visão em camadas de um DAG particiona seus vértices em níveis de modo que cada aresta vá de um nível de número menor para um de número maior. Vértices na mesma camada são independentes entre si, podendo ser executados em paralelo. O número de camadas é igual ao comprimento do caminho mais longo mais um — este é o caminho crítico do DAG, o número mínimo de rodadas sequenciais necessárias para terminar todas as tarefas, mesmo com paralelismo ilimitado. Esta calculadora produz a visualização em camadas automaticamente sempre que a entrada for um DAG.

Detecção de ciclo

Se o grafo contiver um ciclo direcionado, nenhuma ordenação topológica será possível. Nossa calculadora relata o caminho exato do ciclo (ex: A → B → C → A) e destaca as arestas do ciclo em vermelho na visualização. Remover qualquer aresta única no ciclo é suficiente para restaurar a aciclicidade.

Formatos de entrada

Lista de arestas

Escreva cada aresta direcionada como origem -> destino, separada por vírgulas ou quebras de linha. Variantes de seta aceitas: ->, →, =>, -->, :. Você também pode encadear arestas: A -> B -> C é um atalho para A->B e B->C. Rótulos de vértices podem ser letras, dígitos, sublinhados, hifens e pontos.

Lista de adjacência

Escreva cada vértice, dois pontos e seus sucessores diretos (vértices para os quais ele aponta). Um vértice sem sucessores ainda precisa de sua linha, como D:.

Como usar esta calculadora

1. Escolha um formato: Alterne entre lista de arestas e lista de adjacência com os botões de rádio.
2. Insira o grafo: Cole seus dados ou clique em um dos exemplos rápidos (ordem de vestir, pré-requisitos de cursos, alvos de build, um grafo com ciclo e mais).
3. Escolha um algoritmo: Kahn lexicográfico para uma ordem única e reproduzível; ordem de inserção para preservar a ordenação de entrada; DFS pós-ordem para o método clássico de busca em profundidade; ou Mostrar todos para ver cada ordenação lado a lado.
4. Clique em "Ordenar Topologicamente": A ordenação, detecção de ciclo, visualização em camadas, comprimento do caminho crítico, número total de ordenações válidas e um grafo interativo aparecerão abaixo.
5. Explore: Pressione Play para ver cada vértice ser emitido um passo por vez. Os emblemas de grau de entrada atualizam ao vivo. Arraste qualquer nó para reorganizar o layout.

Aplicações no mundo real

Sistemas de build e compiladores

Ferramentas como make, Bazel, Gradle e npm ordenam topologicamente seus alvos de build para que cada alvo seja compilado apenas após todas as suas dependências. Um ciclo no grafo de dependência é geralmente relatado como um erro fatal — o sistema de build não consegue decidir por onde começar.

Agendamento de tarefas

Gerentes de projeto usam DAGs para capturar dependências de tarefas. A ordenação topológica fornece uma ordem de execução válida, e a visão em camadas fornece o número mínimo de rodadas sob paralelismo ilimitado. A maior cadeia é o caminho crítico que determina a duração do projeto.

Planejamento de pré-requisitos de cursos

Um catálogo de cursos universitários é um DAG: as arestas são relações de pré-requisito. Uma ordem topológica é um plano de estudos válido, e as camadas dizem aos alunos quais conjuntos de cursos eles podem fazer em paralelo durante cada semestre.

Recalculo de planilhas

Quando uma célula muda, uma planilha deve recomputar cada célula a jusante na ordem de dependência — uma ordenação topológica do DAG de dependência de células. Referências circulares (ciclos) são rejeitadas pela aplicação.

Gerenciadores de pacotes e carregadores de plugins

Apt, pip, Homebrew, Maven e inúmeros frameworks de plugins resolvem a ordem de instalação ou carregamento ordenando topologicamente seus DAGs de dependência.

Resolução de símbolos e agendamento de instruções

Compiladores usam ordenação topológica para ordenar declarações, e CPUs usam DAGs de dependência de dados para agendar instruções no buffer de reordenação sem violar perigos de dados.

Contando ordenações topológicas

Para um DAG com n vértices, o número de ordenações topológicas válidas distintas pode variar de 1 (para uma cadeia totalmente ordenada) a n! (para um grafo sem arestas). Computar a contagem exata é um problema #P-completo em geral, mas para grafos de até 16 vértices esta calculadora os enumera usando uma formulação de programação dinâmica com bitmask: f(S) = Σ f(S ∪ {v}) para todos os v ∉ S cujos predecessores estão todos em S.

Complexidade e desempenho

• Tempo: Tanto o algoritmo de Kahn quanto o DFS pós-ordem rodam em O(|V| + |E|) — linear no tamanho do grafo.
• Espaço: O(|V|) para rastreamento de grau de entrada e a ordem de saída, mais O(|V| + |E|) para a estrutura de adjacência.
• Detecção de ciclo: Integrada em ambos os algoritmos. Kahn detecta ciclos quando |saída| < |V|; DFS os detecta quando uma aresta de retorno (vizinho CINZA) é encontrada.
• Limites nesta ferramenta: até 80 vértices e 800 arestas para visualização interativa. A contagem de ordenações é limitada a 16 vértices.

Perguntas frequentes

O que é uma ordenação topológica?

Uma ordenação topológica de um grafo acíclico direcionado é uma ordenação linear de seus vértices tal que cada aresta direcionada de u para v coloca u antes de v. Representa uma ordem válida para processar tarefas que respeitam suas dependências.

Qual algoritmo esta calculadora utiliza?

A calculadora executa tanto o algoritmo de Kahn quanto o DFS pós-ordem. O algoritmo de Kahn remove repetidamente um vértice com grau de entrada zero e decrementa os graus de entrada de seus sucessores. O DFS pós-ordem executa uma busca em profundidade e inverte a ordem de finalização. Ambos rodam em tempo O(|V| + |E|).

E se o meu grafo tiver um ciclo?

Um grafo com um ciclo direcionado não possui ordenação topológica. A calculadora detecta o ciclo, destaca-o em vermelho na visualização e relata o caminho exato do ciclo para que você possa ver quais arestas remover para tornar o grafo um DAG.

O que é a menor ordem topológica lexicográfica?

Quando muitas ordenações topológicas são válidas, a menor lexicograficamente é obtida sempre escolhendo o vértice alfabeticamente menor cujo grau de entrada é zero em cada etapa. O modo padrão de Kahn desta calculadora retorna esta ordenação única, que é estável e fácil de reproduzir.

O que é a visualização por camada ou nível?

A visualização por camadas agrupa vértices pelo comprimento do caminho mais longo a partir de qualquer fonte. Vértices na mesma camada não têm dependência entre si, portanto podem ser executados em paralelo. O número de camadas é igual à maior cadeia de dependência mais um e fornece o número mínimo de rodadas paralelas necessárias para terminar todas as tarefas.

Um grafo pode ter muitas ordenações topológicas válidas?

Sim. Se em qualquer etapa o algoritmo de Kahn tiver múltiplos vértices com grau de entrada zero, qualquer um deles pode ser escolhido em seguida. Esta calculadora conta o número exato de ordenações topológicas distintas para grafos de até 16 vértices.

Qual a diferença entre o algoritmo de Kahn e o DFS pós-ordem?

O de Kahn funciona de cima para baixo: ele escolhe repetidamente fontes (grau de entrada 0) e as emite primeiro. O DFS pós-ordem funciona de baixo para cima: ele termina os sumidouros primeiro e os anexa à ordem. Ambos são O(|V| + |E|) e produzem ordenações topológicas válidas, mas tipicamente diferentes. O de Kahn é mais fácil de paralelizar e de adaptar para ordenação lexicográfica; o DFS é mais fácil de combinar com outras análises baseadas em DFS, como componentes fortemente conectados.

Qual o tamanho máximo de grafo que esta ferramenta suporta?

A calculadora suporta até 80 vértices e 800 arestas. A contagem do número total de ordenações topológicas válidas é limitada a 16 vértices porque o problema é #P-completo e o espaço de estados cresce como 2ⁿ. A visualização interativa e a animação do algoritmo escalam suavemente até o tamanho total.

Leitura Adicional

• Ordenação topológica — Wikipédia
• Grafo acíclico dirigido — Wikipédia
• Busca em profundidade — Wikipédia
• Método do caminho crítico — Wikipédia
• Componente fortemente conexo — Wikipédia