Ordinamento topologico
Ogni volta che installi un software, compili un programma o pianifichi un progetto, qualcosa deve capire che cosa fare per primo. Se il compito B ha bisogno del compito A, A deve venire prima. Un ordinamento topologico trasforma una rete di regole come queste in un'unica linea retta.
L'idea
Disegna ogni compito come un nodo e ogni regola «A prima di B» come una freccia da A a B. Un ordine topologico è una fila di tutti i nodi in cui ogni freccia punta verso destra. Si chiama ordinamento perché mette le cose in ordine, ma a differenza dell'ordinamento di numeri deve rispettare solo le frecce: i nodi che nessuna catena di frecce collega possono venire in qualsiasi ordine.
Quando è impossibile
Se le frecce formano un ciclo, per esempio A prima di B, B prima di C e C prima di A, allora A dovrebbe venire prima di se stesso. Quindi un ordine topologico esiste esattamente quando il grafo non ha cicli orientati. Un grafo così si chiama grafo aciclico orientato, o DAG. Entrambi i metodi qui sotto trovano un ciclo se c'è, il che li rende anche un comodo test per i cicli.
Un esempio
Prendi le frecce A → C, B → C, B → D, C → E e D → E. L'algoritmo di Kahn conta le frecce entranti: A e B non ne hanno, quindi A va per primo, poi B. Togliere le frecce di B libera C e D, che seguono, e poi E: l'ordine A, B, C, D, E. Il metodo DFS visita A, poi C, poi E; E viene completato per primo, poi C, poi A, e ognuno va in testa. Poi visita B e D, che vengono completati e vanno davanti a loro: l'ordine B, D, A, C, E. Entrambi gli ordini sono corretti.
Kahn o DFS?
L'algoritmo di Kahn, pubblicato da Arthur Kahn nel 1962, lavora in avanti: sa sempre quali compiti possono iniziare adesso, il che è adatto alla pianificazione, e può scegliere tra i compiti liberi con qualsiasi regola, per esempio l'ordine alfabetico. Il metodo DFS, reso popolare da Robert Tarjan nel 1976, lavora all'indietro partendo dalla fine e ha bisogno solo di una visita in profondità. Entrambi richiedono un tempo che cresce con il numero di nodi più archi.
Usi
Gli strumenti di build come make compilano i file dopo i file da cui dipendono. I gestori di pacchetti installano le librerie in ordine di dipendenza. I fogli di calcolo ricalcolano una cella dopo le celle usate dalla sua formula. Le università controllano che i prerequisiti dei corsi si possano soddisfare, i compilatori ordinano le istruzioni, e le pipeline di dati eseguono ogni passo dopo che i suoi input sono pronti. Il comando Unix tsort esegue da solo un ordinamento topologico.
Provalo
Apri l'app e premi Passo. Le frecce dicono quale nodo deve venire prima di quale. Con l'algoritmo di Kahn, il numero su ogni nodo conta le sue frecce entranti rimaste, e i nodi liberi sono blu. Con il metodo DFS, i nodi blu sono in visita e quelli verdi sono collocati. L'ordine cresce nella fila sotto il grafo. Spunta Aggiungi un ciclo e guarda entrambi i metodi scoprire che non esiste nessun ordine.
Domande frequenti
Che cosa significa topologico qui?
Il nome viene dalla topologia, lo studio di come le cose sono collegate più che della loro forma esatta. L'ordine dipende solo da quali nodi sono collegati da frecce, non da dove sono disegnati.
Come trovo il ciclo quando non c'è un ordine?
Il metodo DFS lo mostra direttamente: l'arco verso un nodo ancora in visita, insieme al percorso dei nodi in visita, è il ciclo. L'algoritmo di Kahn dice solo quali nodi sono bloccati; una ricerca tra questi trova il ciclo.
Posso scegliere un ordine preciso tra quelli validi?
Sì. Nell'algoritmo di Kahn, quando più nodi sono liberi, scegli quello che preferisci, per esempio la lettera più piccola o il compito più urgente. Con una coda di priorità si ottiene l'ordine che viene prima in ordine alfabetico.
Come si usa l'ordinamento topologico con i percorsi più brevi?
Su un grafo aciclico orientato, rilassare gli archi di ogni nodo in ordine topologico trova tutti i percorsi più brevi da una partenza in una sola passata, anche con archi negativi, più in fretta di Dijkstra o Bellman–Ford.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova l'ordinamento topologico