Ordenação Topológica com o Algoritmo de Kahn
Ordene tarefas que dependem de outras.
Ordenação Topológica com o Algoritmo de Kahn é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que é uma ordenação topológica
Uma ordenação topológica lista todos os nós de um grafo direcionado de modo que cada aresta aponte de um nó anterior para um posterior. Pense em tarefas que vêm antes das tarefas que dependem delas.
Apenas DAGs são permitidos
Isso funciona somente em um DAG, um grafo direcionado acíclico. Se existir um ciclo, nenhuma ordenação válida poderá satisfazer todas as dependências.
A ideia do grau de entrada
O algoritmo de Kahn baseia-se no grau de entrada: quantas arestas apontam para um nó. Um nó com grau de entrada zero não tem dependências pendentes.
Conte cada grau de entrada
Primeira passagem: percorra todas as arestas e conte quantas vezes cada nó aparece como destino. Isso fornece o grau de entrada de cada nó.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Inicialize a fila de nós prontos
Todo nó com grau de entrada zero está pronto imediatamente, então coloque todos eles em uma fila para começar.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Processe um nó
Faça pop de um nó pronto e faça append dele à sua ordenação. Agora isso é seguro porque nada que ainda resta depende dele.
u = q.popleft()
order.append(u)Libere os vizinhos
Para cada vizinho, diminua o grau de entrada em um. Quando um vizinho chegar a zero, ele ficará pronto e entrará na fila.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Repita até a fila ficar vazia
Continue fazendo pop e liberando nós até a fila ficar vazia. A ordenação cresce com um nó seguro por vez, até que todos sejam colocados.
Detecte um ciclo gratuitamente
Se a ordenação final tiver menos de n nós, um ciclo prendeu os demais. O algoritmo de Kahn oferece detecção de ciclos sem custo adicional.
if len(order) < n:
print('cycle exists')O tempo de execução
Cada nó e cada aresta são visitados uma vez, então o algoritmo de Kahn executa em O(V + E). Isso funciona até para grafos com milhões de arestas.
Muitas ordenações válidas
Quando vários nós estão prontos ao mesmo tempo, qualquer um deles pode ser escolhido em seguida. Por isso, um DAG costuma ter muitas ordenações topológicas válidas, não apenas uma.
Verificação rápida
Você termina o algoritmo de Kahn, mas a ordenação tem menos de n nós. O que isso significa?
Recapitulação: algoritmo de Kahn
Conte os graus de entrada, coloque os nós com grau zero na fila, faça pop de um nó, diminua o grau dos vizinhos e repita. Essa é uma ordenação topológica simples em O(V+E). 🚀
Perguntas Frequentes
A aula “Ordenação Topológica com o Algoritmo de Kahn” é grátis?
Sim — o texto completo de “Ordenação Topológica com o Algoritmo de Kahn” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Ordenação Topológica com o Algoritmo de Kahn”?
Ordene tarefas que dependem de outras. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Ordenação Topológica com o Algoritmo de Kahn”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordenação Topológica com o Algoritmo de Kahn
- Detecte Ciclos em Grafos Direcionados
- Componentes Fortemente Conexos
- Pontes e Pontos de Articulação