- Attuale
- Libero o in visita
- Collocato
- Ciclo
Ordinamento topologico
Le calze prima delle scarpe, le fondamenta prima dei muri, un corso prima del corso che lo richiede. Un ordinamento topologico mette i nodi di un grafo con archi a senso unico in una fila in cui ogni arco punta in avanti. Scegli l'algoritmo di Kahn o il metodo DFS e procedi passo per passo per vedere l'ordine crescere, poi aggiungi un ciclo per vedere perché allora nessun ordine è possibile. Premi Avvia per guardare l'ordine crescere, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Ogni arco è a senso unico, come mostra la sua freccia: leggilo come «questo viene prima di quello». Scegli il metodo: l'algoritmo di Kahn colloca prima i nodi senza archi entranti, e il numero su ogni nodo dice quanti archi entranti ha ancora; il metodo DFS colloca ogni nodo in testa appena tutto ciò che viene dopo è collocato. La riga sotto il grafo è l'ordine finora. Spunta Aggiungi un ciclo per vedere come ogni metodo ne trova uno. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scegli l'algoritmo di Kahn o il metodo DFS.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
- Guarda l'ordine crescere sotto il grafo. Spunta Aggiungi un ciclo per vedere come ogni metodo ne trova uno.
Algoritmo di Kahn
Conta, per ogni nodo, quanti archi puntano su di esso. Un nodo che non ne ha non dipende da nulla, quindi può andare per primo. Colloca un nodo così e togli i suoi archi uscenti: i nodi su cui puntavano hanno ora un arco entrante in meno, e alcuni possono arrivare a zero e diventare liberi. Continua a collocare nodi liberi finché non ne resta nessuno. Se alcuni nodi non sono mai stati liberati, si aspettano a vicenda in un ciclo, e non esiste un ordine topologico.
Il metodo DFS
Esegui una visita in profondità da ogni nodo non visitato. Un nodo è completato quando tutto ciò che si raggiunge da lì è completato, quindi tutto ciò che deve venire dopo è già collocato. Metti ogni nodo completato in testa all'ordine, e l'ordine viene giusto. Se la visita segue un arco verso un nodo in cui si trova ancora, quell'arco chiude un ciclo, e di nuovo non esiste un ordine.
Domande frequenti
Che cos'è un ordinamento topologico?
Un ordine dei nodi di un grafo orientato in cui ogni arco va da un nodo precedente a uno successivo. Se gli archi significano «deve venire prima», è un ordine in cui si possono svolgere tutti i compiti.
Quando esiste un ordine topologico?
Esattamente quando il grafo non ha cicli orientati: è un grafo aciclico orientato, o DAG. Con un ciclo, ogni nodo del ciclo dovrebbe venire prima di se stesso.
L'ordine topologico è unico?
Di solito no. Quando due nodi non sono collegati da una catena di archi, uno qualsiasi dei due può andare per primo, quindi un grafo può avere molti ordini validi. L'algoritmo di Kahn e il metodo DFS ne danno spesso di diversi.
Quanto è veloce un ordinamento topologico?
Entrambi i metodi esaminano ogni nodo e ogni arco un numero fisso di volte, quindi il lavoro cresce con il numero di nodi più il numero di archi.
Il mio grafo viene inviato da qualche parte?
No. Il grafo viene creato e ordinato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor