Ordinamento topologico DFS post-order

Il secondo algoritmo classico per l'ordinamento topologico utilizza DFS con elaborazione post-order. Dopo aver esplorato completamente tutti i vicini di un nodo e i rispettivi discendenti, inserisca il nodo in uno stack. Quando tutti i nodi sono stati elaborati, estragga gli elementi dallo stack per leggere l'ordine topologico. Un nodo inserito nello stack dopo che tutte le sue dipendenze sono state elaborate deve comparire per primo nell'ordine; perciò il post-order inverso è l'ordinamento topologico.

Consideri un grafo delle dipendenze in cui il corso A richiede il corso B. Quando la DFS visita A, richiama innanzitutto la DFS su B. B non ha prerequisiti, quindi termina per primo e viene inserito per primo nello stack. Poi termina A, che viene a sua volta inserito nello stack. L'estrazione dallo stack restituisce A prima di B, ma alla fine invertiamo l'ordine e otteniamo B prima di A: prima B, poi A. Il post-order inserisce le dipendenze prima degli elementi che dipendono da esse, quindi lo stack invertito è un ordinamento topologico valido.

Utilizzi tre stati per i nodi visitati: WHITE (0) = non visitato, GREY (1) = attualmente in elaborazione (nello stack delle chiamate DFS), BLACK (2) = elaborato completamente. Un arco all'indietro, cioè un arco verso un nodo GREY, indica un ciclo. Gli archi verso nodi BLACK sono sicuri, perché quei nodi sono già stati esplorati completamente. Questo schema a tre colori rileva correttamente tutti i cicli nei grafi orientati.

Utilizzi una DFS ricorsiva che assegna un colore ai nodi, li inserisce in uno stack in post-order e restituisce False quando rileva un ciclo. Dopo aver visitato tutti i nodi, lo stack, invertito, fornisce l'ordine topologico.

Il limite di ricorsione di Python, 1000 per impostazione predefinita, può essere problematico per i grafi di grandi dimensioni. Una DFS iterativa che utilizza uno stack esplicito evita questo problema. Il punto chiave è inserire inizialmente (node, False); quando l'elemento viene estratto con valore False, inserisca (node, True), che significa "tornerò qui dopo l'esplorazione", quindi inserisca tutti i vicini non visitati con valore False. Quando l'elemento viene estratto con valore True, assegni al nodo il colore BLACK e lo inserisca nello stack del risultato.

Entrambi gli algoritmi hanno complessità O(V + E). Differenze principali: Kahn's (BFS) produce naturalmente i nodi nell'ordine delle dipendenze più immediate e offre un rilevamento dei cicli più semplice, tramite il controllo della lunghezza. La DFS post-order funziona in modo ricorsivo e rileva esplicitamente gli archi all'indietro. Kahn's è preferibile quando si desidera ottenere il risultato nell'ordine diretto, senza doverlo invertire. La DFS è preferibile quando serve il post-order completo per altri scopi, come il rilevamento delle SCC. Entrambe le soluzioni sono accettabili nei colloqui tecnici.

In un albero, il post-order visita il sottoalbero sinistro, poi il sottoalbero destro e infine la radice. In un DAG, la DFS in post-order visita tutte le dipendenze di un nodo prima di elaborare il nodo stesso: è la stessa idea generalizzata a più predecessori e a una struttura di grafo arbitraria. La radice di un albero DFS, cioè il nodo di partenza, viene inserita dopo tutti i suoi discendenti, quindi appare per prima nello stack invertito: è la posizione topologica corretta per un nodo senza predecessori.

Alien Dictionary: data una lista ordinata di parole in una lingua aliena, ricavi l'ordinamento dei caratteri. Confronti le parole adiacenti carattere per carattere per trovare la prima differenza: questa determina un arco c1 → c2, che significa che c1 viene prima di c2. Raccolga tutti questi archi ed esegua un ordinamento topologico per ottenere l'ordinamento dei caratteri della lingua aliena. Se esiste un ciclo, l'ordinamento non è valido.

Alcuni problemi richiedono un ordinamento topologico che soddisfi vincoli aggiuntivi, ad esempio il mantenimento dell'ordine relativo degli elementi nella lista originale. Combini l'algoritmo di Kahn's con una coda con priorità personalizzata o con un pre-ordinamento: mantenga l'ordine relativo originale utilizzando un ordinamento stabile sugli elementi della coda a ogni passaggio. Queste varianti con vincoli verificano una comprensione più approfondita della flessibilità dell'algoritmo.

Nei problemi da colloquio, alcune espressioni indicano un ordinamento topologico: "date le dipendenze", "prerequisiti", "ordinamento delle attività", "ordine di compilazione", "è possibile completare tutte le attività?", "trovare una sequenza valida". Se il problema richiede di ordinare elementi di cui alcuni devono precedere altri, costruisca un grafo orientato e applichi l'ordinamento topologico di Kahn's o quello basato su DFS. Il rilevamento dei cicli è spesso un requisito secondario dello stesso problema.

DFS e Kahn's possono produrre ordinamenti topologici validi ma diversi per lo stesso grafo. Entrambi sono corretti: un DAG può avere più ordinamenti topologici validi. Per verificare la correttezza, controlli che per ogni arco u → v del grafo, u compaia prima di v nell'ordine prodotto. Nei problemi da colloquio che richiedono un ordine specifico, ad esempio quello lessicograficamente minore, utilizzi Kahn's con un min-heap: il post-order della DFS non produce naturalmente l'ordine lessicograficamente minore.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: l'ordinamento topologico con DFS in post-order inserisce i nodi dopo aver esplorato tutte le loro dipendenze, la marcatura a tre colori (WHITE/GREY/BLACK) rileva i cicli tramite gli archi all'indietro verso i nodi GREY e l'inversione dello stack in post-order produce un ordinamento topologico valido. Ora applicheremo direttamente l'ordinamento topologico ai problemi Course Schedule I e II.