Detecte Ciclos em Grafos Direcionados
Colore nós para encontrar arestas de retorno.
Detecte Ciclos em Grafos Direcionados é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 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.
Por que os ciclos importam
Um ciclo direcionado significa que as dependências retornam sobre si mesmas. Detectar um ciclo mostra que não pode existir uma ordenação topológica nem um cronograma válido.
Grafo não direcionado é diferente
A detecção de ciclos aqui depende da direção. Seguir arestas no sentido errado não conta, portanto os truques para grafos não direcionados não se aplicam.
A ideia das três cores
Atribua a cada nó uma de três cores: branco significa não visitado, cinza significa em processamento e preto significa totalmente concluído.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nCinza significa estar na pilha
Um nó cinza está no caminho atual do DFS. Você entrou nele, mas ainda não terminou de explorar todos os seus descendentes.
Entre em um nó
Quando o DFS chegar a um nó, pinte-o de cinza antes de explorá-lo. Isso marca o nó como parte do caminho ativo.
def dfs(u):
color[u] = GRAYO sinal da aresta de retorno
Se você chegar a um vizinho que já está cinza, encontrou uma aresta de retorno para o caminho atual. Isso é um ciclo.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleRecurses no nó branco
Um vizinho branco é novo, então recurses nele. Propague True assim que qualquer chamada mais profunda indicar um ciclo.
elif color[v] == WHITE and dfs(v):
return TruePreto é seguro
Um vizinho preto já foi totalmente explorado e não contém ciclos, então você pode ignorá-lo. Visitá-lo novamente apenas desperdiçaria tempo.
Conclua um nó
Depois de tratar todos os vizinhos, pinte o nó de preto. Ele deixa o caminho ativo e é marcado como concluído.
color[u] = BLACK
return FalseCubra todos os componentes
O grafo pode ser desconexo, então inicie o DFS a partir de cada nó ainda branco para garantir que todo o grafo seja verificado.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Tenha cuidado com o limite de recursão
Grafos profundos podem estourar a pilha de recursão do Python. Aumente o limite ou reescreva o DFS usando uma pilha explícita.
import sys
sys.setrecursionlimit(300000)Verificação rápida
Durante o DFS, você chega a um vizinho que está cinza. O que acabou de encontrar?
Recapitulação: detecção de ciclos
Pinte os nós de branco, depois de cinza e então de preto. Um vizinho cinza durante o DFS é uma aresta de retorno, o que prova a existência de um ciclo direcionado. 🔁
Perguntas Frequentes
A aula “Detecte Ciclos em Grafos Direcionados” é grátis?
Sim — o texto completo de “Detecte Ciclos em Grafos Direcionados” é 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 “Detecte Ciclos em Grafos Direcionados”?
Colore nós para encontrar arestas de retorno. 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 2 de 4.
Quanto tempo leva a aula “Detecte Ciclos em Grafos Direcionados”?
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