- Atual
- Livre ou em visita
- Colocado
- Ciclo
Ordenação topológica
As meias antes dos sapatos, as fundações antes das paredes, uma disciplina antes da disciplina que precisa dela. Uma ordenação topológica põe os nós de um grafo com arestas de sentido único numa fila em que cada aresta aponta para a frente. Escolha o algoritmo de Kahn ou o método DFS e avance passo a passo para ver a ordem crescer, e adicione um ciclo para ver porque é que então nenhuma ordem é possível. Prima Reproduzir para ver a ordem crescer, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Cada aresta tem um só sentido, como mostra a sua seta: leia-a como «isto vem antes daquilo». Escolha o método: o algoritmo de Kahn coloca primeiro os nós sem arestas de entrada, e o número em cada nó é quantas arestas de entrada ainda tem; o método DFS coloca cada nó à frente assim que tudo o que vem depois dele está colocado. A linha por baixo do grafo é a ordem até agora. Marque Adicionar um ciclo para ver como cada método encontra um. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escolha o algoritmo de Kahn ou o método DFS.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
- Veja a ordem crescer por baixo do grafo. Marque Adicionar um ciclo para ver como cada método encontra um.
Algoritmo de Kahn
Conte, para cada nó, quantas arestas apontam para ele. Um nó sem nenhuma não depende de nada, por isso pode ir primeiro. Coloque esse nó e remova as suas arestas de saída: os nós para onde apontavam ficam com menos uma aresta de entrada, e alguns podem chegar a zero e ficar livres. Continue a colocar nós livres até não restar nenhum. Se alguns nós nunca ficaram livres, esperam uns pelos outros num ciclo, e não existe ordem topológica.
O método DFS
Faça uma pesquisa em profundidade a partir de cada nó não visitado. Um nó fica concluído quando tudo o que se alcança a partir dele está concluído, por isso tudo o que tem de vir depois dele já está colocado. Ponha cada nó concluído no início da ordem, e a ordem sai certa. Se a pesquisa seguir uma aresta para um nó em que ainda está, essa aresta fecha um ciclo, e mais uma vez não existe ordem.
Perguntas frequentes
O que é uma ordenação topológica?
Uma ordenação dos nós de um grafo dirigido em que cada aresta vai de um nó anterior para um posterior. Se as arestas significam «tem de vir antes», é uma ordem em que todas as tarefas podem ser feitas.
Quando existe uma ordem topológica?
Exatamente quando o grafo não tem ciclos dirigidos: é um grafo acíclico dirigido, ou DAG. Com um ciclo, cada nó do ciclo teria de vir antes de si próprio.
A ordem topológica é única?
Normalmente não. Sempre que dois nós não estão ligados por uma cadeia de arestas, qualquer um pode ir primeiro, por isso um grafo pode ter muitas ordens válidas. O algoritmo de Kahn e o método DFS dão muitas vezes ordens diferentes.
Quão rápida é uma ordenação topológica?
Ambos os métodos examinam cada nó e cada aresta um número fixo de vezes, por isso o trabalho cresce com o número de nós mais o número de arestas.
O meu grafo é enviado para algum lado?
Não. O grafo é criado e ordenado no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor