Ordinamento topologico con l’algoritmo di Kahn
Ordinare le attività che dipendono da altre
Ordinamento topologico con l’algoritmo di Kahn è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.
Che cos'è l'ordinamento topologico
Un ordinamento topologico elenca ogni nodo di un grafo orientato in modo che ogni arco vada da un nodo precedente a uno successivo. Si pensi alle attività da completare prima di quelle che dipendono da esse.
Solo i DAG
Questo funziona solo su un DAG, cioè un grafo orientato aciclico. Se esiste un ciclo, non può esistere alcun ordinamento valido che soddisfi tutte le dipendenze.
L'idea del grado entrante
L'algoritmo di Kahn si basa sul grado entrante: il numero di archi che entrano in un nodo. Un nodo con grado entrante pari a zero non ha dipendenze non ancora soddisfatte.
Contare ogni grado entrante
Prima fase: si percorrono tutti gli archi e si conta quante volte ogni nodo compare come destinazione. In questo modo si ottiene il grado entrante di ogni nodo.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Inizializzare la coda dei nodi pronti
Ogni nodo con grado entrante pari a zero è subito pronto, quindi lo si inserisce in una coda per iniziare.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Elaborare un nodo
Si estrae un nodo pronto e lo si aggiunge all'ordinamento. Ora è sicuro farlo, perché nessun nodo ancora da elaborare dipende da esso.
u = q.popleft()
order.append(u)Liberare i vicini
Per ogni vicino, si riduce di uno il suo grado entrante. Quando un vicino raggiunge zero, diventa pronto e viene inserito nella coda.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Ripetere fino a svuotare la coda
Si continua a estrarre nodi e a liberare i vicini finché la coda non si svuota. L'ordinamento cresce aggiungendo un nodo sicuro alla volta, fino a includerli tutti.
Rilevare un ciclo gratuitamente
Se l'ordinamento finale contiene meno di n nodi, un ciclo ha intrappolato i nodi rimanenti. L'algoritmo di Kahn offre il rilevamento dei cicli senza costi aggiuntivi.
if len(order) < n:
print('cycle exists')Il tempo di esecuzione
Ogni nodo e ogni arco vengono visitati una volta, quindi l'algoritmo di Kahn ha complessità O(V + E). Questo lo rende adatto a grafi con milioni di archi.
Molti ordinamenti validi
Quando più nodi sono pronti contemporaneamente, qualunque nodo può essere scelto come successivo. Perciò un DAG ha spesso molti ordinamenti topologici validi, non uno solo.
Verifica rapida
Si conclude l'algoritmo di Kahn, ma l'ordinamento contiene meno di n nodi. Che cosa significa?
Riepilogo: algoritmo di Kahn
Si contano i gradi entranti, si inseriscono in coda quelli pari a zero, si estrae un nodo, si decrementano i gradi dei vicini e si ripete. Questo è un ordinamento topologico semplice in O(V+E). 🚀
Domande Frequenti
La lezione «Ordinamento topologico con l’algoritmo di Kahn» è gratuita?
Sì — il testo completo di «Ordinamento topologico con l’algoritmo di Kahn» è 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 «Ordinamento topologico con l’algoritmo di Kahn»?
Ordinare le attività che dipendono da altre 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 1 di 4.
Quanto tempo richiede la lezione «Ordinamento topologico con l’algoritmo di Kahn»?
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