Rilevare cicli nei grafi orientati
Colorare i nodi per trovare gli archi all’indietro
Rilevare cicli nei grafi orientati è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Perché i cicli sono importanti
Un ciclo orientato indica che le dipendenze tornano su se stesse. Rilevarne uno significa che non può esistere alcun ordinamento topologico né una pianificazione valida.
Con i grafi non orientati è diverso
Qui il rilevamento dei cicli riguarda la direzione. Seguire gli archi nel verso sbagliato non conta, quindi i metodi per i grafi non orientati non si applicano.
L'idea dei tre colori
Si assegna a ogni nodo uno di tre colori: bianco significa non visitato, grigio significa in elaborazione, nero significa completamente elaborato.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nIl grigio indica che il nodo è nello stack
Un nodo grigio si trova nel percorso DFS corrente. Lo si è raggiunto, ma non si è ancora terminata l'esplorazione di tutti i suoi discendenti.
Entrare in un nodo
Quando la DFS raggiunge un nodo, lo si colora di grigio prima di esplorarlo. In questo modo lo si contrassegna come parte del percorso attivo.
def dfs(u):
color[u] = GRAYIl segnale dell'arco all'indietro
Se si raggiunge un vicino già grigio, si è trovato un arco all'indietro verso il percorso corrente. Questo indica un ciclo.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleRicorrere sui nodi bianchi
Un vicino bianco non è ancora stato visitato, quindi si ricorre su di esso. Si restituisce True non appena una chiamata più profonda segnala un ciclo.
elif color[v] == WHITE and dfs(v):
return TrueIl nero è sicuro
Un vicino nero è stato completamente esplorato e non contiene cicli, quindi lo si può ignorare. Visitarlo di nuovo farebbe solo perdere tempo.
Terminare un nodo
Dopo aver gestito tutti i vicini, si colora il nodo di nero. In questo modo esce dal percorso attivo e viene contrassegnato come completato.
color[u] = BLACK
return FalseCoprite ogni componente
Il grafo potrebbe essere disconnesso, quindi si avvia la DFS da ogni nodo ancora bianco per assicurarsi di controllarlo interamente.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Attenzione al limite di ricorsione
I grafi profondi possono causare un overflow dello stack di ricorsione di Python. Si aumenti il limite oppure si riscriva la DFS usando uno stack esplicito.
import sys
sys.setrecursionlimit(300000)Verifica rapida
Durante la DFS si raggiunge un vicino che è attualmente grigio. Che cosa si è appena trovato?
Riepilogo: rilevamento dei cicli
Si colorano i nodi di bianco, poi di grigio e infine di nero. Un vicino grigio durante la DFS è un arco all'indietro, che dimostra l'esistenza di un ciclo orientato. 🔁
Domande Frequenti
La lezione «Rilevare cicli nei grafi orientati» è gratuita?
Sì — il testo completo di «Rilevare cicli nei grafi orientati» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Rilevare cicli nei grafi orientati»?
Colorare i nodi per trovare gli archi all’indietro Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Rilevare cicli nei grafi orientati»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinamento topologico con l’algoritmo di Kahn
- Rilevare cicli nei grafi orientati
- Componenti fortemente connesse
- Ponti e punti di articolazione