Calcolatore di Ordinamento Topologico
Calcola un ordinamento topologico di un grafo aciclico diretto (DAG) utilizzando l'algoritmo di Kahn o la DFS. Rileva i cicli, riporta il percorso del ciclo, crea una vista a livelli per l'esecuzione parallela, supporta l'ordinamento lessicografico più piccolo e anima ogni passaggio su un grafo interattivo.
Il tuo ad blocker ci impedisce di mostrare annunci
MiniWebtool è gratuito grazie agli annunci. Se questo strumento ti è stato utile, sostienici con Premium (senza annunci + più veloce) oppure inserisci MiniWebtool.com nella whitelist e ricarica la pagina.
- Oppure passa a Premium (senza annunci)
- Consenti gli annunci per MiniWebtool.com, poi ricarica
Calcolatore di Ordinamento Topologico
Il Calcolatore di Ordinamento Topologico calcola una disposizione lineare dei vertici di un grafo aciclico diretto (DAG) tale che per ogni arco diretto da u a v, u preceda v. Inserisci il tuo grafo come elenco di archi o lista di adiacenza e lo strumento restituirà l'ordine topologico utilizzando l'algoritmo di Kahn o il DFS post-order, rileverà cicli (con il relativo percorso), raggrupperà i compiti in strati di esecuzione parallela, conterà il numero di ordinamenti validi e animerà ogni passaggio su un grafo interattivo.
Cos'è un ordinamento topologico?
Dato un grafo diretto G = (V, E), un ordinamento topologico è una disposizione lineare v₁, v₂, …, vₙ dei suoi vertici tale che per ogni arco diretto (u → v), u appare prima di v nella disposizione. Un ordinamento topologico esiste se e solo se il grafo non ha cicli diretti — ovvero, il grafo è un DAG. L'ordinamento è raramente unico: un grafo può avere molti ordinamenti topologici validi quando più vertici hanno grado di entrata zero contemporaneamente.
per ogni arco (u → v) in E: posizione(u) < posizione(v)
Algoritmi utilizzati da questo calcolatore
Algoritmo di Kahn (basato su BFS, 1962)
L'algoritmo di Kahn è l'ordinamento topologico più intuitivo. In ogni fase sceglie un vertice con grado di entrata zero (nessun arco in entrata), lo aggiunge all'output e lo "rimuove" dal grafo decrementando il grado di entrata di ciascuno dei suoi successori. Quando più vertici hanno grado di entrata zero, la scelta può usare un min-heap (fornendo l'ordinamento lessicograficamente più piccolo) o una coda FIFO (fornendo l'ordine di inserimento). L'algoritmo di Kahn gira in tempo O(|V| + |E|) e funge anche da rilevatore di cicli: se qualche vertice ha ancora un grado di entrata > 0 dopo che la coda si è svuotata, il grafo contiene un ciclo.
Q ← { v ∈ V : indeg(v) = 0 }
L ← [ ]
mentre Q non è vuota:
u ← Q.pop()
L.append(u)
per ogni arco u → v:
indeg(v) -= 1
se indeg(v) = 0: Q.push(v)
se |L| < |V|: segnala ciclo
altrimenti: restituisci L
DFS post-order (Tarjan, 1976)
L'algoritmo DFS esegue una ricerca in profondità e, ogni volta che un vertice finisce (cioè tutti i suoi successori sono stati esplorati), viene inserito in uno stack. Invertendo lo stack alla fine si ottiene un ordinamento topologico valido. Il rilevamento dei cicli è naturale: incontrare un vertice ancora in corso (contrassegnato come GRIGIO) significa che è stato trovato un arco all'indietro, quindi il grafo non è un DAG. Il DFS post-order gira anch'esso in tempo O(|V| + |E|).
per ogni vertice u in V: colore[u] ← BIANCO
L ← stack vuoto
per ogni vertice u in V:
se colore[u] = BIANCO: visita(u)
restituisci reverse(L)
visita(u):
colore[u] ← GRIGIO
per ogni arco u → v:
se colore[v] = GRIGIO: segnala ciclo
se colore[v] = BIANCO: visita(v)
colore[u] ← NERO; L.push(u)
Strati di esecuzione parallela
Una vista stratificata di un DAG divide i suoi vertici in livelli in modo che ogni arco vada da un livello con numero inferiore a uno con numero superiore. I vertici nello stesso strato sono indipendenti l'uno dall'altro, quindi possono essere eseguiti in parallelo. Il numero di strati è pari alla lunghezza del percorso più lungo più uno: questo è il percorso critico del DAG, il numero minimo di round sequenziali necessari per completare tutte le attività anche con parallelismo illimitato. Questo calcolatore produce automaticamente la vista a strati quando l'input è un DAG.
Rilevamento dei cicli
Se il grafo contiene un ciclo diretto, non è possibile alcun ordinamento topologico. Il nostro calcolatore riporta il percorso esatto del ciclo (es. A → B → C → A) ed evidenzia gli archi del ciclo in rosso sulla visualizzazione. La rimozione di un singolo arco del ciclo è sufficiente per ripristinare l'aciclicità.
Formati di input
Elenco di archi
Scrivi ogni arco diretto come sorgente -> destinazione, separato da virgole o a capo. Varianti di freccia accettate: ->, →, =>, -->, :. Puoi anche concatenare gli archi: A -> B -> C è un'abbreviazione per A->B e B->C. Le etichette dei vertici possono essere lettere, cifre, underscore, trattini e punti.
C -> D
Camicia -> Cravatta -> Giacca
Lista di adiacenza
Scrivi ogni vertice, due punti e i suoi successori diretti (i vertici a cui punta). Un vertice senza successori richiede comunque la sua riga, ad esempio D:.
B: D
C: D
D:
Come usare questo calcolatore
- Scegli un formato: Passa da elenco archi a lista adiacenza con i pulsanti radio.
- Inserisci il grafo: Incolla i tuoi dati o clicca su uno degli esempi rapidi (ordine vestizione, prerequisiti corsi, target build, grafo con ciclo, ecc.).
- Scegli un algoritmo: Kahn lessicografico per un ordine unico e riproducibile; ordine di inserimento per preservare l'ordine di input; DFS post-order per il metodo classico; o Mostra tutti per vederli affiancati.
- Clicca su "Ordina Topologicamente": L'ordinamento, il rilevamento cicli, la vista a strati, la lunghezza del percorso critico, il numero totale di ordinamenti validi e un grafo interattivo appariranno sotto.
- Esplora: Premi Play per guardare ogni vertice venire emesso un passo alla volta. I badge del grado di entrata si aggiornano in tempo reale. Trascina i nodi per riorganizzare il layout.
Applicazioni nel mondo reale
Sistemi di build e compilatori
Strumenti come make, Bazel, Gradle e npm ordinano topologicamente i loro target di build in modo che ogni target venga compilato solo dopo tutte le sue dipendenze. Un ciclo nel grafo delle dipendenze viene solitamente segnalato come errore fatale.
Pianificazione delle attività
I project manager utilizzano i DAG per catturare le dipendenze dei compiti. L'ordinamento topologico fornisce un ordine di esecuzione valido, mentre la vista a strati indica il numero minimo di round con parallelismo illimitato. La catena più lunga è il percorso critico che determina la durata del progetto.
Pianificazione dei prerequisiti dei corsi
Un catalogo di corsi universitari è un DAG: gli archi rappresentano le relazioni di prerequisito. Un ordine topologico è un piano di studi valido, e gli strati dicono agli studenti quali insiemi di corsi possono frequentare in parallelo durante ogni semestre.
Ricalcolo del foglio di calcolo
Quando una cella cambia, un foglio di calcolo deve ricalcolare ogni cella a valle nell'ordine di dipendenza — un ordinamento topologico del DAG delle dipendenze delle celle. I riferimenti circolari (cicli) vengono rifiutati dall'applicazione.
Package manager e caricatori di plugin
Apt, pip, Homebrew, Maven e innumerevoli framework di plugin risolvono l'ordine di installazione o caricamento ordinando topologicamente i loro DAG di dipendenza.
Risoluzione dei simboli e scheduling delle istruzioni
I compilatori usano l'ordinamento topologico per ordinare le dichiarazioni, e le CPU usano i DAG delle dipendenze dei dati per pianificare le istruzioni nel buffer di riordino senza violare i rischi sui dati.
Contare gli ordinamenti topologici
Per un DAG con n vertici, il numero di ordinamenti topologici validi distinti può variare da 1 (per una catena totalmente ordinata) a n! (per un grafo senza archi). Calcolare il conteggio esatto è in generale un problema #P-completo, ma per grafi fino a 16 vertici questo calcolatore li enumera utilizzando una formulazione di programmazione dinamica con bitmask: f(S) = Σ f(S ∪ {v}) su tutti i v ∉ S i cui predecessori sono tutti in S.
Complessità e prestazioni
- Tempo: Sia l'algoritmo di Kahn che il DFS post-order girano in O(|V| + |E|) — lineare nella dimensione del grafo.
- Spazio: O(|V|) per il tracciamento del grado di entrata e l'ordine di output, più O(|V| + |E|) per la struttura di adiacenza.
- Rilevamento cicli: Integrato in entrambi gli algoritmi. Kahn rileva i cicli quando |output| < |V|; DFS li rileva quando viene trovato un arco all'indietro (vicino GRIGIO).
- Limiti in questo strumento: fino a 80 vertici e 800 archi per la visualizzazione interattiva. Il conteggio degli ordinamenti è limitato a 16 vertici.
Domande frequenti
Cos'è un ordinamento topologico?
Un ordinamento topologico di un grafo aciclico diretto è un ordinamento lineare dei suoi vertici tale che ogni arco diretto da u a v pone u prima di v. Rappresenta un ordine valido per elaborare compiti rispettando le loro dipendenze.
Quale algoritmo utilizza questo calcolatore?
Il calcolatore esegue sia l'algoritmo di Kahn che il DFS post-order. L'algoritmo di Kahn rimuove ripetutamente un vertice con grado di entrata zero e decrementa i gradi dei suoi successori. Il DFS post-order esegue una ricerca in profondità e inverte l'ordine di completamento. Entrambi girano in tempo O(|V| + |E|).
Cosa succede se il mio grafo ha un ciclo?
Un grafo con un ciclo diretto non ha ordinamento topologico. Il calcolatore rileva il ciclo, lo evidenzia in rosso e riporta il percorso esatto in modo da poter identificare quali archi rimuovere.
Qual è l'ordinamento topologico lessicograficamente più piccolo?
Quando esistono più ordinamenti validi, quello lessicograficamente più piccolo si ottiene scegliendo sempre il vertice alfabeticamente più piccolo tra quelli con grado di entrata zero. La modalità predefinita di Kahn restituisce questo ordine unico.
Cos'è la vista a strati o a livelli?
La vista a strati raggruppa i vertici in base alla lunghezza del percorso più lungo da una sorgente. I vertici nello stesso strato possono essere eseguiti in parallelo. Il numero di strati indica il numero minimo di fasi sequenziali necessarie.
Un grafo può avere molti ordinamenti topologici validi?
Sì. Se in qualsiasi fase l'algoritmo di Kahn ha più vertici con grado di entrata zero, la scelta è libera. Questo calcolatore conta il numero esatto di ordinamenti distinti per grafi fino a 16 vertici.
Qual è la differenza tra l'algoritmo di Kahn e il DFS post-order?
Kahn lavora top-down: sceglie ripetutamente le sorgenti (grado 0). Il DFS post-order lavora bottom-up: finisce prima i pozzi e li prepone all'ordine. Entrambi sono O(|V| + |E|), ma producono spesso ordini diversi. Kahn è più facile da parallelizzare; DFS è utile per altre analisi come le componenti fortemente connesse.
Qual è la dimensione massima del grafo supportata?
Supporta fino a 80 vertici e 800 archi. Il conteggio degli ordinamenti è limitato a 16 vertici perché il problema è #P-completo e lo spazio degli stati cresce come 2ⁿ. L'animazione e la visualizzazione scalano fluidamente fino alla dimensione massima.
Ulteriori letture
- Ordinamento topologico — Wikipedia
- Grafo aciclico diretto — Wikipedia
- Ricerca in profondità — Wikipedia
- Metodo del percorso critico — Wikipedia
- Componente fortemente connessa — Wikipedia
Cita questo contenuto, pagina o strumento come:
"Calcolatore di Ordinamento Topologico" su https://MiniWebtool.com/it/calcolatore-di-ordinamento-topologico/ di MiniWebtool, https://MiniWebtool.com/
dal team di miniwebtool. Aggiornato: 20 apr 2026
Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.
Altri strumenti correlati:
Operazioni matematiche avanzate:
- Calcolatore di Antilogaritmo
- Calcolatore di funzione Beta
- Calcolatore del Coefficiente Binomiale
- Calcolatrice di distribuzione binomiale
- Calcolatore Bitwise
- Calcolatore del Teorema Centrale del Limite
- Calcolatore di combinazione In Primo Piano
- Calcolatore di Funzione di Errore Complementare
- Calcolatrice di Numeri Complessi
- Calcolatore di Entropia
- Calcolatore della funzione di errore
- Calcolatore di decadimento esponenziale
- Calcolatore della crescita esponenziale
- Calcolatore dell'Integrale Esponenziale
- calcolatore-di-esponenti-alta-precisione
- Calcolatrice del Fattoriale
- Calcolatore della Funzione Gamma
- Calcolatore del Rapporto Aureo
- Calcolatore del tempo di dimezzamento
- Calcolatore del Tasso di Crescita Percentuale
- Calcolatore di Permutazione
- Calcolatrice della Distribuzione di Poisson
- Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
- Calcolatrice delle probabilità
- Calcolatrice di Distribuzione di Probabilità
- Calcolatore di Proporzioni
- Calcolatore di formula quadratica
- Calcolatrice Scientifica In Primo Piano
- Calcolatore di notazioni scientifiche
- Calcolatore di Cifre Significative Nuovo
- Calcolatore di Somme di Cubi
- Calcolatore di somme di numeri interi positivi
- Calcolatore di Somme di Quadrati
- Generatore di Tabella di Verità Nuovo
- Calcolatore di Teoria degli Insiemi Nuovo
- Generatore di Diagramma di Venn (3 Insiemi) Nuovo
- Calcolatore del Teorema Cinese del Resto Nuovo
- Calcolatore della Funzione Toziente di Eulero Nuovo
- Calcolatore dell'Algoritmo Euclideo Esteso Nuovo
- Calcolatore dell'Inverso Moltiplicativo Modulare Nuovo
- Calcolatore di Frazioni Continue Nuovo
- Calcolatore del Percorso più Breve di Dijkstra Nuovo
- Calcolatore dell'Albero Ricoprente Minimo Nuovo
- Validatore di Sequenza di Gradi di Grafo Nuovo
- Calcolatore di Derangement (Sottofattoriale) Nuovo
- Calcolatore di Numeri di Stirling Nuovo
- Calcolatore del Principio dei Cassetti Nuovo
- Calcolatore Distribuzione Stazionaria Catena di Markov Nuovo
- Calcolatore di Arrotondamento Nuovo
- Calcolatore Distribuzione Binomiale Negativa Nuovo
- Calcolatore Permutazioni con Ripetizione Nuovo
- Calcolatore Esponenziazione Modulare Nuovo
- Calcolatore Radice Primitiva Nuovo
- Semplificatore di Algebra Booleana Nuovo
- Risolutore di Mappa di Karnaugh (K-Map) Nuovo
- Calcolatore di Colorazione di Grafi Nuovo
- Calcolatore di Ordinamento Topologico Nuovo
- Calcolatore di Matrice di Adiacenza Nuovo
- Calcolatore Inclusione-Esclusione Nuovo
- Risolutore di Programmazione Lineare Nuovo
- Risolutore del Commesso Viaggiatore (TSP) Nuovo
- Verificatore di Cammino Hamiltoniano Nuovo