Rilevare cicli nei grafi orientati
Colorare i nodi per trovare gli archi all’indietro
Rilevare cicli nei grafi orientati è una lezione Coding Interview Prep 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Rilevare cicli nei grafi orientati»?
Colorare i nodi per trovare gli archi all’indietro Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep 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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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