Algoritmo de Kahn - Ordenação topológica
A ordenação topológica estabelece uma sequência linear de vértices a partir de um grafo acíclico dirigido (DAG). Em outras palavras, para cada aresta direcionada de um nó A para um nó B, o nó A deve aparecer antes do nó B na ordenação.
Esta organização é utilizado em cenários onde existem dependências entre tarefas, como no gerenciamento de projetos, resolução de dependências de software e agendamento de cursos.
Algoritmo
O algoritmo baseia-se na ideia de identificar e processar sequencialmente os vértices que não possuem dependência de entrada, ou seja, se aqueles que possuem o grau de entrada zero.
Sequência de passos:
- Calcular o grau de entrada dos vértices.
- Identificar os vértices iniciais: crie uma fila e adicione todos os vértices que possuem um grau de entrada igual a zero.
- Processar a fila: enquanto a fila estiver vazia
- Remova o vértice da fila (chamado de
). - Adicione
ao final do vetor de solução (representação da ordenação topológica). - Para cada vértice
adjacente a - Decremente o grau de entrada de
em 1. - Se o grau de entrada de
se tornar 0, adicione na fila.
- Decremente o grau de entrada de
- Remova o vértice da fila (chamado de