Ordinamento topologico

In teoria dei grafi un ordinamento topologico (in inglese topological sort) è un ordinamento lineare di tutti i vertici di un grafo diretto. I nodi di un grafo si definiscono ordinati topologicamente se i nodi sono disposti in modo tale che ogni nodo viene prima di tutti i nodi collegati ai suoi archi uscenti. L'ordinamento topologico non è un ordinamento totale, poiché la soluzione può non essere unica. Nel caso peggiore infatti si possono avere $n!$ ordinamenti topologici diversi che corrispondono a tutte le possibili permutazioni degli $n$ nodi. È possibile ordinare topologicamente un grafo se e solo se non contiene cicli (cioè solo se è un grafo aciclico diretto), e sono noti algoritmi per determinare un ordinamento topologico in tempo lineare.

Esempi

L'applicazione canonica dell'ordinamento topologico risiede nel problema di pianificare l'esecuzione di una sequenza di attività in base alle loro dipendenze. Le attività sono rappresentate dai nodi di un grafo: vi è un arco tra $x$ e $y$ se l'attività $x$ deve essere completata prima che possa iniziare l'esecuzione dell'attività $y$. Un ordinamento topologico del grafo così ottenuto fornisce un ordine in cui eseguire le attività.

Alcuni ordinamenti topologici validi per il grafo mostrato a sinistra sono: 7, 5, 3, 11, 8, 2, 9, 10 (graficamente da sinistra a destra e dall'alto al basso) 3, 5, 7, 8, 11, 2, 9, 10 (prima i nodi con i valori minori della loro numerazione) 3, 7, 8, 5, 11, 10, 2, 9 5, 7, 3, 8, 11, 10, 9, 2 7, 5, 11, 3, 10, 8, 9, 2 (prima i nodi con i valori maggiori della loro numerazione) 7, 5, 11, 2, 3, 8, 9, 10

Algoritmi

Uno degli algoritmi classici per ordinare topologicamente un grafo è basato sul concetto di visita in profondità (ricerca depth-first). L'algoritmo di ordinamento topologico effettua una visita in profondità del grafo (a partire da ognuno dei nodi senza archi entranti) e, terminata la visita di ogni vertice, lo inserisce in testa ad una lista concatenata L. Al termine dell'esecuzione, questa lista conterrà i nodi ordinati. In pseudocodice:

L ← Lista vuota (conterrà i nodi ordinati)
S ← Insieme di tutti i nodi senza archi entranti
for each nodo n in S do
    visit(n) 
return L

dove la procedura visit è definita come

function visit(nodo n)
    if n non è ancora stato visitato then
        marca n come visitato
        for each nodo m con un arco da n a m do
            visit(m)
        aggiungi n a L

Si noti che l'algoritmo di cui è fornito lo pseudocodice non è in grado di determinare il caso (di errore) in cui nel grafo sono presenti cicli, ma può farlo con semplici modifiche.

L'algoritmo harvtxt, descritto da Kahn (1962), sceglie i vertici rispettando l'ordinamento topologico. Inizialmente, costruisce un insieme di vertici che non hanno archi entranti (grado entrante=0); dato che il grafo è aciclico esiste almeno uno di questi nodi. Poi:

L ← lista vuota che conterrà gli elementi ordinati
S ← insieme di nodi senza archi entranti
while S non è vuoto do
    rimuovi un vertice u da S
    inserisci u in L
    for each vertice v con un arco e da u a v do
        rimuovi arco e dal grafo
        if v non ha altri archi entranti then
            inserisci v in S
if il grafo ha ancora archi then
    ritorna un errore (il grafo ha almeno un ciclo)
else 
    ritorna L (l'ordinamento topologico)

Se il grafo è un DAG, la soluzione è contenuta nella lista L (non necessariamente unica). Altrimenti, il grafo ha almeno un ciclo ed è impossibile ottenere un ordinamento topologico.

L'insieme S può essere un set, una coda o una pila dato che non importa in quale ordine vengono estratti i vertici. Differenti soluzioni sono dovute all'ordine in cui i nodi vengono estratti da S.

Complessità

Per un grafo G(V,E) dove V è l'insieme dei nodi e E l'insieme degli archi, entrambi gli algoritmi presentano una complessità lineare O(|V|+|E|), mentre l'inserimento di ciascuno dei |V| vertici in testa alla lista concatenata richiede tempo costante. Complessivamente, quindi, gli algoritmi impiegano tempo O(|V|+|E|).

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003, ISBN 88-256-1421-7.