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.

⚡ Prova un esempio:

Catena lineare Ordine vestizione Prerequisiti corsi Routine mattutina Target di build Campione adiacenza Con un ciclo DAG di pipeline

Formato di input

→ Elenco archi

⧇ Lista adiacenza

Dati del grafo

Formato archi: A -> B (accetta anche →, =>, :). Max 80 vertici / 800 archi.

Formato adiacenza: A: B, C, D — un vertice per riga, seguito dai suoi successori diretti.

Algoritmo

L'algoritmo di Kahn (lessicografico) fornisce un ordine unico e riproducibile. Il DFS post-order è il classico metodo di ricerca in profondità.

Embed Calcolatore di Ordinamento Topologico Widget

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.

Definizione di ordine topologico

Una permutazione (v₁, v₂, …, v_n) di V è topologica sse
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.

Algoritmo di Kahn (pseudocodice)

Kahn(G):
  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|).

DFS post-order (pseudocodice)

DFS-Topo(G):
  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.

A -> B, B -> C, A -> C
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:.

A: B, C
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

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.

Calcolatore di Ordinamento Topologico

Calcolatore di Ordinamento Topologico

Cos'è un ordinamento topologico?

Algoritmi utilizzati da questo calcolatore

Algoritmo di Kahn (basato su BFS, 1962)

DFS post-order (Tarjan, 1976)

Strati di esecuzione parallela

Rilevamento dei cicli

Formati di input

Elenco di archi

Lista di adiacenza

Come usare questo calcolatore

Applicazioni nel mondo reale

Sistemi di build e compilatori

Pianificazione delle attività

Pianificazione dei prerequisiti dei corsi

Ricalcolo del foglio di calcolo

Package manager e caricatori di plugin

Risoluzione dei simboli e scheduling delle istruzioni

Contare gli ordinamenti topologici

Complessità e prestazioni

Domande frequenti

Cos'è un ordinamento topologico?

Quale algoritmo utilizza questo calcolatore?

Cosa succede se il mio grafo ha un ciclo?

Qual è l'ordinamento topologico lessicograficamente più piccolo?

Cos'è la vista a strati o a livelli?

Un grafo può avere molti ordinamenti topologici validi?

Qual è la differenza tra l'algoritmo di Kahn e il DFS post-order?

Qual è la dimensione massima del grafo supportata?

Ulteriori letture

Operazioni matematiche avanzate:

Strumenti in primo piano: