Prerequisiti
Esami, corsi o attività che richiedono risultati precedenti.
Algoritmi · Grafi orientati
Ordinamento topologico
Se un arco u→v significa “u deve venire prima di v”, un ordinamento topologico dispone tutti i vertici in una sequenza che rispetta ogni dipendenza.
Dal grafo a una sequenza valida
Definizione. Dato un grafo orientato G = (V, E), un ordinamento topologico è una permutazione dei vertici tale che, per ogni arco (u, v) ∈ E, u compare prima di v.
A→C→D→F
L’ordine descrive i vincoli, non necessariamente una cronologia unica. Se A e B non sono collegati da alcun cammino, possono spesso scambiarsi senza invalidare il risultato.
Build system
Compilare una dipendenza prima del modulo che la importa.
Pianificazione
Trovare un ordine ammissibile; le durate richiedono poi ulteriori tecniche.
Esiste se e solo se il grafo è un DAG
Un DAG è un grafo orientato aciclico. Se esiste il ciclo A→B→C→A, ogni vertice dovrebbe precedere sé stesso: il vincolo è impossibile. Viceversa, ogni DAG contiene almeno un vertice con grado entrante zero.
Unicità. L’ordinamento è unico soltanto se a ogni passo esiste un solo vertice disponibile con grado entrante zero. Più scelte indicano più ordinamenti validi.
Algoritmo di Kahn: rimuovere le sorgenti
- Calcola il grado entrante di ogni vertice.
- Inserisci in una coda tutti i vertici con grado entrante 0.
- Estrai un vertice u, aggiungilo all’ordine e “rimuovi” i suoi archi uscenti decrementando i gradi dei vicini.
- Ogni vicino che raggiunge grado 0 entra in coda. Se alla fine mancano vertici, gli archi residui contengono un ciclo.
Laboratorio: costruisci l’ordine
Avanza un’operazione alla volta: i badge sui nodi mostrano il grado entrante residuo, gli archi tratteggiati sono già stati rimossi.
Sintassi: A>C, B>C, F · da 2 a 10 vertici.
Esempi
Coda · grado entrante 0
Ordine prodotto
Gradi entranti residui
Diagnosi
—
- Vertici ordinati
- 0
- Archi rimossi
- 0
- Scelte disponibili
- 0
- Ordine unico?
- —
Perché l’algoritmo è corretto
Scelta sicura
Un vertice di grado entrante 0 non ha predecessori ancora da collocare: può essere il prossimo elemento dell’ordine.
Invariante
La sequenza prodotta rispetta tutti gli archi già rimossi; i gradi memorizzati corrispondono esattamente al grafo residuo.
Ciclo certificato
Se la coda si svuota ma rimangono vertici, ciascuno ha un predecessore residuo. Seguendoli, in un insieme finito, prima o poi si ripete un vertice: esiste un ciclo.
Studio della complessità
| Operazione | Costo | Motivo |
|---|---|---|
| Calcolo dei gradi | Θ(|V| + |E|) | Inizializzazione dei vertici e una scansione degli archi. |
| Coda e rimozioni | Θ(|V| + |E|) | Ogni vertice entra una volta; ogni arco causa un decremento. |
| Tempo totale | Θ(|V| + |E|) | Con liste di adiacenza. |
| Spazio ausiliario | Θ(|V|) | Gradi, coda e risultato; il grafo occupa Θ(|V| + |E|). |
Alternativa DFS e applicazioni
Una DFS può colorare i vertici bianco, grigio e nero: un arco verso un vertice grigio rivela un ciclo; se non ne trova, l’ordine inverso dei tempi di fine è topologico. Ha lo stesso costo Θ(|V| + |E|), ma Kahn rende più espliciti prerequisiti disponibili e parallelismo.
Non è uno scheduler completo. L’ordinamento topologico rispetta le precedenze, ma non ottimizza durata, risorse o numero di attività parallele.
Errori comuni ed esercizi
- Applicarlo a un grafo non orientato o non controllare che il risultato contenga tutti i vertici.
- Credere che un DAG abbia sempre un solo ordine: prova il preset “Più ordini”.
- Ricalcolare ogni grado da zero a ogni passo, facendo salire inutilmente il costo.
Prima di avviare il diamante, elenca tutti gli ordinamenti validi.
Aggiungi F>B alle dipendenze iniziali: in quale momento Kahn riconosce il ciclo?
Come cambieresti la coda per ottenere sempre l’ordine lessicograficamente minimo?