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

É uma ordenação dos vértices de um grafo direcionado tal que para toda aresta direcionada de u para v, u aparece antes de v na ordenação — só possível quando o grafo não tem ciclos.

Como funciona o algoritmo de Kahn?

Ele encontra repetidamente um nó com zero arestas de entrada restantes (sem pré-requisitos não processados), remove-o e o adiciona à ordem de saída, depois diminui o grau de entrada de seus vizinhos, repetindo até que cada nó seja processado.

O que acontece se o grafo tiver um ciclo?

O algoritmo trava — alguns nós sempre terão pelo menos uma aresta de entrada de dentro do ciclo, então nunca são removíveis, e a calculadora informa que nenhuma ordem topológica válida existe.

A ordem topológica é sempre única?

Não — quando vários nós têm zero arestas de entrada ao mesmo tempo, qualquer um deles poderia vir a seguir, então um grafo pode ter várias ordens topológicas válidas. Esta calculadora escolhe uma consistentemente usando desempate alfabético.

Como isso difere do algoritmo de Dijkstra?

O algoritmo de Dijkstra encontra caminhos mais curtos em um grafo ponderado; a ordenação topológica encontra uma ordem de processamento válida em um grafo direcionado baseada puramente na estrutura de dependência, sem noção de peso de aresta ou distância.

O que significa '->' na entrada de arestas?

Indica direção — A->B significa que há uma aresta direcionada de A para B (A deve vir antes de B), diferente do formato não direcionado 'A-B' usado pelas outras ferramentas de grafos do site.

Quantos nós esta calculadora consegue processar?

Esta calculadora suporta até 50 nós, mantendo instantâneo o algoritmo de Kahn enquanto cobre a grande maioria dos grafos de dependência inseridos manualmente.

Onde a ordenação topológica é usada na vida real?

É usada em sistemas de build e compiladores (compilando arquivos em ordem de dependência), gerenciadores de pacotes (instalando dependências antes dos pacotes que precisam delas), agendadores de tarefas, e ordem de avaliação de fórmulas em planilhas.

Calculadora de Ordenação Topológica — Ordene Tarefas por Suas Dependências

Nossa Calculadora de Ordenação Topológica encontra uma ordenação válida dos nós de um grafo direcionado de modo que toda aresta aponte de um nó anterior para um posterior — exatamente a ordenação necessária para agendar tarefas dependentes — usando o algoritmo de Kahn, e informa claramente quando tal ordenação não existe porque o grafo contém um ciclo.

Resposta rápida

Digite seu grafo direcionado como uma lista de arestas para encontrar instantaneamente uma ordem topológica válida via o algoritmo de Kahn, ou detectar que um ciclo torna a ordenação impossível.

Arestas direcionadas (separadas por vírgula)

Digite arestas direcionadas como NóA->NóB, ex. A->B, A->C, B->D.

Como usar Calculadora de Ordenação Topológica — Algoritmo de Kahn Online

1
Digite seu grafo direcionado como uma lista de arestas separadas por vírgula, ex. A->B, A->C, B->D.
2
Clique em 'Calcular' para encontrar uma ordem topológica válida.
3
Revise a ordem resultante, ou a mensagem de ciclo detectado se nenhuma ordem existir.

Por que usar Calculadora de Ordenação Topológica — Algoritmo de Kahn Online?

Uma ordenação topológica organiza os nós de um grafo acíclico direcionado em uma linha onde toda aresta aponta para frente — exatamente a estrutura necessária para agendar tarefas com dependências, compilar arquivos na ordem correta, ou resolver a ordem de instalação de pacotes. O algoritmo de Kahn a encontra diretamente: remove repetidamente qualquer nó sem arestas de entrada restantes e o anexa à ordem, atualizando o grafo restante conforme avança. Se o processo ficar sem nós removíveis antes que todos os nós sejam colocados, o grafo deve conter um ciclo, significando que nenhuma ordenação válida existe — esta calculadora detecta esse caso explicitamente em vez de retornar uma ordem parcial ou incorreta.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Caminho Mais Curto de Dijkstra — Grafos Ponderados Online

Encontre o caminho mais curto e a distância total entre dois nós em um grafo ponderado usando o algoritmo de Dijkstra. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Matriz de Adjacência — Construa uma Matriz de Grafo Online

Construa e exiba a matriz de adjacência de um grafo a partir de uma entrada simples de lista de arestas, junto com sua sequência de graus. Calculadora gratuita, ponderada ou não ponderada.

Verificador de Caminho Hamiltoniano — Visite Cada Nó Uma Vez Online

Verifique se um grafo tem um caminho hamiltoniano — um caminho que visita cada nó exatamente uma vez — via busca com retrocesso. Calculadora gratuita, limitada a grafos de até 10 nós.