Motivation
Lição 2 de 9 do curso Ordenação Topológica - Algoritmos de Grafos da Coddy.
Uma ordem tópologica só existe quando o grafo não possui ciclos. Construímos uma com o algoritmo de Kahn, que remove repetidamente um vértice que não possui arestas de entrada restantes.
Por que aprender Ordenação Topológica?
- Ordenação com restrições: sistemas de build, agendamento de tarefas, pré-requisitos de cursos e recálculo de planilhas dependem disso.
- Detecção de ciclos: se você não conseguir ordenar todos os vértices, o grafo deve conter um ciclo.
- Base para algoritmos de DAG: os caminhos mais curtos e mais longos em um DAG são computados em ordem topológica.
Muitas ordens válidas podem existir. Para obter uma resposta previsível, sempre removemos o vértice de menor número cujo grau de entrada é 0.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
